平衡()二叉树

Question

我需要编写一个方法来确定二叉树是否平衡。所以首先我要确定树的每一面的高度。但是我很难理解如何计算一个子树的最大长度，而不计算子树中的所有节点。这个问题对我来说很难问，所以你们可以理解。

// primary method
public int Height()
{
    int h = height( root );
}

// recursive method
private int height( Node x )
{
    if( x == null ) return 0;
    count++;                   
    height( x.left );
    height( x.right );
    return count;           
}

这是我计算树最大高度的代码。但我不知道如何确定左侧或右侧的高度，而且这种方法似乎计算树本身中的节点数量。

Answer 1

由于return;语句的缘故，这个方法甚至不能编译--您需要返回一个int。

那么，if(x == null)，你应该返回什么呢？一棵空树的高度是多少？

一旦你弄清楚了，假设你的根只有一个左子树(root.right == null)，并且你知道左子树的高度。整个树的高度应该是多少？

如果它只有一个正确的子树呢？

现在，如果两者都有呢？

请注意，这一切都不需要全局计数变量。

Answer 2

高度是1+ max(left.height()，right.height())。

你应该返回一个值而不是设置一个变量(在你的例子中是count)，否则你会发疯的。

Answer 3

节点的高度比其最高的子节点的高度大1(提示:使用Math.max)。