java - 平衡二叉树

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)，并且你知道左子树的高度。整棵树的高度应该是多少？

如果它只有右子树怎么办？

现在，如果两者兼而有之呢？

请注意，您不需要为此使用全局计数变量。