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 的大作中提到】
:
: 多谢， 我也经常犯迷糊。
|
