java - 找出二叉树的直径

Question

我试图在 java 中找到二叉树的直径(树中包含最大节点数的任意两个节点之间的路径长度。)。

我的代码片段:

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。

有人能找出问题出在哪里吗...

Answer 1

public int diameter (Node root)
{
    if (root == null) return 0;
    else return Math.max (
        diameter (root.left), 
        Math.max (
            diameter (root.right),
            height (root.left) + height (root.right) + 1));
}

public int height (Node root)
{
    if (root == null) return 0;
    else return 1 + Math.max (height (root.left), height (root.right));
}