balanced（）二叉树

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

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

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

来源

2011-04-30 Ruben Van St Aden

闻起来像功课！ – CoolBeans 2011-04-30 17:37:42

是的，我知道。但这就是为什么我没有要求孔平衡树，只是高度和概念如何开始balnced树。为什么我的代码出来如此studip？ – 2011-04-30 17:39:34

愚蠢，对不起... – 2011-04-30 17:40:06

由于return;声明 - 这个方法不会编译，所以你需要返回一个int。因此，if(x == null)，你应该返回什么？空树的高度是多少？

一旦你明白了，想象你的根只有一个左子树（root.right == null），并且你知道左子树的高度。整棵树的高度应该是多少？

如果它只有一个正确的子树会怎么样？

现在，如果它有两个呢？

请注意，您不需要全局计数变量。

来源

2011-04-30 17:41:39

好初学者错误与第一个返回值。如果在那里更改我的代码。 – 2011-04-30 17:52:48

高度为1 + max（left.height（），right.height（））。

你应该返回一个值，而不是设置变量（计数，你的情况），否则你会发疯。

来源

2011-04-30 17:42:05 akappa

但我不明白的是，left.height（）和right.height（）只会返回0.如果不计算一个值，他们如何返回一个值？ – 2011-04-30 17:54:18

但我不明白的是，left.height（）和right.height（）将返回0.如果他们不算一个值，他们如何返回一个值？ – 2011-04-30 17:54:19

cuase我说当到达叶子时返回0 – 2011-04-30 17:54:51

节点的高度比其最高子节点的高度大1（提示：使用Math.max）。

来源

2011-04-30 17:42:23 sjr

添加提示我还会指出，你真的想使用递归。

来源

2011-04-30 20:53:26

balanced（）二叉树

回答

相关问题