java - 二叉搜索树的最大高度

Question

所以我需要找到二叉树的最大高度，但由于某种原因，下面提供的代码的结果偏离了 1。例如，如果最大高度为 3，则以下代码将给我 2。如果最大高度为 4结果将是 3。我不知道为什么？计算最大高度时不考虑根，因此我将 leftCounter 和 rightCounter 设置为 0。有什么想法吗？

public int getMaxHeight(BST.TreeNode<E> n) {
    if(n == null) {
        return 0;
    }
    int leftCounter = 0;
    int rightCounter = 0;
    if(n.left != null) {
        leftCounter = getMaxHeight(n.left) +1 ;
    }
    if(n.right != null) {
        rightCounter = getMaxHeight(n.right) +1 ;
    }

    if(leftCounter > rightCounter) {
        return leftCounter;
    }   
    else 
        return rightCounter;    

}

这个二叉树的最大高度应该是3：因为元素 5,9,11。根不计入最大高度。

        15
   _____|____
   10       21 
___|___    __|__ 
9    14   16   24
                |__
                  25

标签： java

Answer 1

您的代码实际上返回了正确的值；只是你误解了树的高度是什么意思。高度是从根到叶的最长路径上的边数，而不是路径上的节点数。所以下面的树

        3
   _____|____
   4         5 
___|___    __|__ 
6     7    8   9

高度为 2，而不是 3。您要查找的是树中的级别数，而不是高度。

public int getNumberOfLevels(BST.TreeNode<E> n) {
    if(n == null) return 0;
    int left = getNumberOfLevels(n.left);
    int right = getNumberOfLevels(n.right);
    return 1 + Math.max(left, right);
}