作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
https://leetcode.com/problems/balanced-binary-tree/
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binarytree in which the depth of the two subtrees of every node never differby more than 1.
public class Solution {
public boolean isBalanced(TreeNode root) {
int ret = getLevel(root);
if(ret < 0)
return false;
return true;
}
public int getLevel(TreeNode node) {
if(node == null)
return 0;
int l = getLevel(node.left);
int r = getLevel(node.right);
if(Math.abs(l - r) > 1)
return -99;
return Math.max(l + 1, r + 1);
}
}
此代码已被接受。但是,如果我用 Integer.MIN_VALUE 替换 -99,我的代码就会失败。错误是什么?
例如
Input: [1,2,null,3,null,4,null,5]
Output: true
Expected: false
最佳答案
您的代码因溢出的整数运算而失败。以下代码片段将演示这一点:
int val = Integer.MIN_VALUE;
System.out.println(val);
val -= 3;
System.out.println(val);
输出:
-2147483648
2147483645
现在考虑一下您的实际代码中发生了什么:
int l = getLevel(node.left);
// l == -2147483648 == Integer.MIN_VALUE assuming your base case is hit
int r = getLevel(node.right);
// assuming positive r, then Math.abs() will return a massively positive number
if (Math.abs(l - r) > 1)
return -99;
换句话说,上面的 if
语句将在它真正应该触发 false
时触发 true
。
解决方案:
如果您将 getLevel()
方法修改为以下内容,您应该可以避免遇到的问题:
public int getLevel(TreeNode node) {
if(node == null)
return 0;
int l = getLevel(node.left);
int r = getLevel(node.right);
if ( (l < 0 ^ r < 0) || Math.abs(l - r) > 1) {
// you can simply return -1 here, since an actual
// level should never have a negative value
return -1;
}
else {
return Math.max(l + 1, r + 1);
}
}
关于java - 为什么 Integer.MIN_VALUE 在平衡二叉树上失败?有什么问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34304223/
我是一名优秀的程序员,十分优秀!