1

我得到了一个用于实现 Set 的二叉搜索树类。它具有所有基本功能，插入、删除和检查特定值是否存在。还提供了用于树的 Node 类。该节点有一个未使用的类变量height。

class TreeNode{
    .......
    public int height;
    .......
}

这是节点类的过度简化版本。现在我应该编写一个新类，通过使用它来扩展此类的功能，height以便跟踪每个节点的高度，其中高度为：

  • 0，如果节点没有子树，
  • -1 为空
  • 1+ 最大子树的高度。

这里的问题是我不能修改给我的代码，我也不能简单地复制大部分现有代码并修改它以满足我的需要，即我必须调用超类函数add()然后添加一些代码来更新高度，并且这段代码应该只向整个函数的运行时添加一个常量。我想出了一个我调用的解决方案，super.add()然后我沿着搜索路径搜索新添加的元素以更新高度。尽管这可行，但它是一个非常混乱的解决方案。

我目前的解决方案如下：

  • Call super.add()，它本身是一个递归函数（BST 的标准 add 函数）
  • 现在元素已添加，调用一个私有辅助函数，该函数获取已添加的值，递归搜索它，然后沿该搜索路径更新高度信息。

我只是想在这里提示一下，因为我觉得我缺少一些东西，而且我觉得我遇到了精神障碍。避免发布源代码。实际上是迫使我思考的反问题的答案也值得赞赏。

4

0 回答 0