为什么Integer.MIN_VALUE在平衡二叉树上失败了？窃听器是什么？
为什么Integer.MIN_VALUE在平衡二叉树上失败了？窃听器是什么？
提问于 2015-12-16 04:58:22
https://leetcode.com/problems/balanced-binary-tree/
给定二叉树，确定它是否是高度平衡的. 对于这个问题，高度平衡二叉树被定义为一个二叉树，其中每个节点的两个子树的深度不超过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);
}
}此代码已被接受。然而，如果我用替换-99，我的代码就会失败。是什么虫子？
例如：
输入: 1,2，空，3，空，4，空，5 输出:真 预期:假
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-12-16 05:07:27
您的代码正在失败，因为整数算法正在溢出。下面的代码片段将演示这一点：
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语句将触发true，而它确实应该触发false。
解决方案：
如果将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);
}
}Stack Overflow用户
发布于 2015-12-16 05:10:13
在某些情况下，它可能会因溢出而失效。如果l是零，r是Integer.MIN_VALUE，那么l-r实际上是负的，因为它溢出了。结果，条件将失败，下一条语句返回MIN_VALUE+1和zero+1的最大值。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34304223
复制相关文章
相似问题
腾讯云开发者
