Javaで二分木の直径(ノードの最大数を含むツリー内の任意の2つのノード間のパスの長さ)を見つけようとしています。
私のコードスニペット:
public int diametre(Node node, int d)
{
if(node==null)
return 0;
lh=diametre(node.left, d);
rh=diametre(node.right, d);
if(lh+rh+1>d)
d=lh+rh+1;
return findMax(lh, rh)+1;
}
主な方法:
System.out.println( bst.diametre(root,0) );
ロジック:実際にはポストオーダーロジック。変数「d」は、サブツリーの直径を示します(その反復で)。より大きな値が見つかったときに更新されます。「lh」は、左サブツリーの高さを指します。「rh」は、右のサブツリーの高さを指します。
しかし、それは間違った出力を与えます。
考慮されるツリー:
5
/ \
/ \
1 8
\ /\
\ / \
3 6 9
アイドル出力:5
しかし、このコードは3を与えています。
問題がどこにあるのかを誰かが理解できますか...