问一个leetcode上面binary tree的题目# JobHunting - 待字闺中
c*r
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)的解
做到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)的解
