二叉搜索树的高度

Question

我已经编写了用于计算BST高度的代码，但它给了我错误的答案。结果是3，但我期待它是4.请有人指出我的逻辑有缺陷吗？ （我将叶节点的高度定义为零，因此高度=边数）。

public static int getHeight(Node root){ 
    if(root == null || (root.right == null && root.right == null)) return 0; 
    int leftHeight = getHeight(root.left); 
    int rightHeight = getHeight(root.right); 
    return 1 + ((leftHeight >= rightHeight) ? leftHeight : rightHeight); 
} 

的元素在一个空BST加入顺序如下：

20, 50, 35, 44, 9, 15, 62, 11, 13 

因此，我希望它应该是这样的：

 20 
/ \ 
/ \ 
9  50 
    \ /\ 
    15 35 62 
/ \ 
11  44 
    \ 
    13 

编辑：发现的bug。我曾写过

(root.right == null && root.right == null) 

，而不是

(root.left == null && root.right == null) 

感谢彼得·霍尔指出来。

Answer 1

这是一个简单的错字。你正在检查right == null两次，当你几乎肯定意味着left == null其中之一。

I.e.这个条件：

if(root == null || (root.right == null && root.right == null)) return 0; 

应该是：

if(root == null || (root.right == null && root.left == null)) return 0; 

，这将给你你想要的答案。