バイナリ検索ツリーの高さ

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 
/ \ 
/ \ 
9  50 
    \ /\ 
    15 35 62 
/ \ 
11  44 
    \ 
    13 

編集：バグを発見

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

だから私は、それは次のようになりますことを期待しています。私はそれを指摘するために

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

の代わりに、ピーター・ホールへ

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

感謝を書いていました。

Answer 1

これは簡単な入力ミスです。あなたはright == nullを2回確認していますが、そのうちの1つがほぼ確実に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; 

。