二叉搜索树递归方法

Question

我的任务是搜索并找到二叉搜索树的高度。为了解决这个问题，我想出了以下解决方案。

static int countL = 0 ;
static int countR = 0 ;
public static int getHeight(Node root) {

    if (root.left != null) {
        countL++;

        getHeight(root.left);
    }

    if (root.right != null) {
        countR++;

        getHeight(root.right);
    }

    count = Math.max(countL, countR);

    return count;
}

不是最优雅的，但它解决了某些树的问题。在网上搜索我找到了一个替代解决方案。除了更优雅的代码之外，我上面的代码与下面可以看到的代码有什么区别？在寻求成为更熟练的编码员的过程中，减少代码行数的最佳方法是什么。我的任务是了解我哪里出错了，以及下面的代码与我的相比有什么不同

private static int getHeight(Node root){
int heightLeft = 0;
int heightRight = 0;

if (root.left != null) {
    heightLeft = getHeight(root.left) + 1;
}
if (root.right != null) {
    heightRight = getHeight(root.right) + 1;
}
return (heightLeft > heightRight ? heightLeft : heightRight);
}

Answer 1

1.实施不正确

你的实现实际上是不正确的。当 countL 和 countR 都为 0 时，它只会在第一次调用 getHeight 时起作用。这是因为静态变量绑定到 class，而不是对象（像 non-static 变量）或函数的作用域（像第二个解决方案）。

说在第一次调用 getHeight 之后，countL 是 3，countR 是 4。当你第二次调用它时，那些变量永远不会被重置，所以一棵树深度 1 将 return 4.

最后，您的解决方案对于 getHeight(null) 也失败了。

2。静态变量是 anti-pattern

尽可能避免 classes 中的静态变量，因为它们是全局状态。有关完整说明，请参阅 this thread。

3。第二种解决方案更容易阅读

如您所见，第二个解决方案更易于阅读。这是出于三个原因：

所有逻辑都完全包含在函数中，而您的逻辑使用全局状态。
变量命名更好：heightLeft比countL更具语义。
它更短。

如果您有兴趣，这里有一个更简洁的解决方案：

public int getHeight(Node root) {
        if(root == null){
            return 0;
        }
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }

祝您 Java-learning 冒险愉快！

Answer 2

在您的第一个解决方案中，您递增了 countL 和 countR 计数器，而没有考虑您到目前为止遍历的树的高度。让我们以下面的倾斜树为例

   1.   => CountL = 1;  CountR = 0
  /.   
 2.     => CountL = 2;  CountR = 0
/ 
3.      => CountL = 3;  CountR = 0
 \
  4.    => CountL = 3; CountR = 1

如果在递增 countR 时查看最后一步，忽略遍历左侧节点所覆盖的高度。

您的第二个解决方案是 bottom-up 方法，在每个级别，我们比较左右高度和 return 最大值。

希望它有助于理解这两种解决方案之间的区别！

二叉搜索树递归方法

Binary Search Tree recursion methods

java

recursion

binary-search-tree