2017-06-25 20 views
2

私は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) 

感謝を書いていました。

+0

カスケード形式でBSTを表示できませんか。挿入が正しく行われていますか? –

+0

スペースバーが壊れていませんか? – Water

+0

@WillemVanOnsemはい、挿入が正しく行われ、コードの1つおきの部分を1つずつチェックしました。このブロックには唯一の瑕疵がなければなりません。 –

答えて

2

これは簡単な入力ミスです。あなたは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; 

+0

バグを指摘してくれてありがとう。 –

関連する問題