求二叉树的直径 [英] Find the diameter of a binary tree

问题描述

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

I am trying to find the diameter of a binary tree (Path length between any two nodes in the tree containing maximum number of nodes.) in 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"是指:右子树的高度.

Logic: Its actually post-order logic. variable 'd' refers to the diameter of the sub-tree (In that iteration.). It will be updated as and when some larger value found. 'lh' refers to : Left sub tree's height. 'rh' refers to : right sub tree's height.

但是它给出了错误的输出.

But its giving wrong output.

考虑的树:

   5
  / \
 /   \
1     8
 \    /\
  \  /  \
  3  6   9

空闲输出:5

但是此代码给出了3.

能不能弄清楚问题出在哪里...

Can some one figure out where the problem is...

推荐答案

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));
}

这篇关于求二叉树的直径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！