c*****r 发帖数: 108 | 1 最近打算开始做leetcode了。
做到determine a binary tree is balanced 这道题的时候,发现online judge可能少
考虑了一种情况。(另外这个题目在crack上面有,4th edition 2010版本上的答案明显
错的。新的版本我没看过。)
下面是我看到leetcode论坛上的一段code(是错的), 然而online judge pass了:
public class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
private int height(TreeNode root)
{
if(root == null)
return 0;
int leftHeight = height(root.left);
if(leftHeight == -1)
return -1;
int rightHeight = height(root.right);
if(rightHeight == -1)
return -1;
if(Math.abs(leftHeight - rightHeight) > 1)
return -1;
return 1 + Math.max(leftHeight, rightHeight);
}
}
我想的一种情况是这样的:
1
/ \
2 3
/ \ / \
4 5 7 8
/ / \ / \
6 12 13 9 10
/
6
这个树明显不balance 但是用以上的code却判断出来是balanced。
有可能是我最近做题做米糊了,想发出来让大家看看是不是我miss了什么地方。
另外,1337大神还有peking2大神 求指教一个O(n)的解 |
c********t 发帖数: 5706 | 2 It is a balanced tree by definition.
★ 发自iPhone App: ChineseWeb 7.8
【在 c*****r 的大作中提到】 : 最近打算开始做leetcode了。 : 做到determine a binary tree is balanced 这道题的时候,发现online judge可能少 : 考虑了一种情况。(另外这个题目在crack上面有,4th edition 2010版本上的答案明显 : 错的。新的版本我没看过。) : 下面是我看到leetcode论坛上的一段code(是错的), 然而online judge pass了: : public class Solution { : public boolean isBalanced(TreeNode root) { : return height(root) != -1; : } : private int height(TreeNode root)
|
s***y 发帖数: 203 | |
i**********e 发帖数: 1145 | 4 这是问题给的 "Height-Balanced binary tree" 的定义:
“a height-balanced binary tree is defined as a binary tree in which the
DEPTH of the two subtrees of EVERY node never differ by more than 1.”
请重复读清楚问题至少三遍,然后再看看你画的图,你就明白了 :)
【在 c*****r 的大作中提到】 : 最近打算开始做leetcode了。 : 做到determine a binary tree is balanced 这道题的时候,发现online judge可能少 : 考虑了一种情况。(另外这个题目在crack上面有,4th edition 2010版本上的答案明显 : 错的。新的版本我没看过。) : 下面是我看到leetcode论坛上的一段code(是错的), 然而online judge pass了: : public class Solution { : public boolean isBalanced(TreeNode root) { : return height(root) != -1; : } : private int height(TreeNode root)
|
l********7 发帖数: 30 | 5 刚才我也在看这个题,也同样迷糊了。
按照这个定义来看cc上给的那个算法是对的
LZ举的这个例子,如果定义balanced binary tree为:任意两个叶子节点的lvl必须相
差不超过1的话
是不是可以加入两个static变量在函数里,min_leaf_lvl和max_leaf_lvl记录所有叶节
点的层,遍历整个树的同时更新这两个值,最后看看是不是( max_left_lvl - min_
leaf_lvl ) <= 1 |
s**x 发帖数: 7506 | 6
多谢, 我也经常犯迷糊。
【在 i**********e 的大作中提到】 : 这是问题给的 "Height-Balanced binary tree" 的定义: : “a height-balanced binary tree is defined as a binary tree in which the : DEPTH of the two subtrees of EVERY node never differ by more than 1.” : 请重复读清楚问题至少三遍,然后再看看你画的图,你就明白了 :)
|
c*****r 发帖数: 108 | 7 嗯 我觉得是不是可以这样。 用一个stack 进行DFS。
然后没到一个leaf 记录一下stack的size。
最后比较所记录的stack的最大最小值是否相差小于等于1.
【在 l********7 的大作中提到】 : 刚才我也在看这个题,也同样迷糊了。 : 按照这个定义来看cc上给的那个算法是对的 : LZ举的这个例子,如果定义balanced binary tree为:任意两个叶子节点的lvl必须相 : 差不超过1的话 : 是不是可以加入两个static变量在函数里,min_leaf_lvl和max_leaf_lvl记录所有叶节 : 点的层,遍历整个树的同时更新这两个值,最后看看是不是( max_left_lvl - min_ : leaf_lvl ) <= 1
|
c*****r 发帖数: 108 | 8 是啊 多谢leetcode大侠了。
我找出了balanced binary tree的定义了。 它的定义是比较open的。 leaf到root的
距离不同的BTree有不同的定义。
【在 s**x 的大作中提到】 : : 多谢, 我也经常犯迷糊。
|