s******3
发帖数: 61 | 1 原先的OJ很容易通过，
public class Solution {
public boolean isValidBST(TreeNode root) {
return rec(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean rec(TreeNode root, int min, int max) {
if (root == null) return true;
if (root.val <= min || root.val >= max) return false;
return rec(root.left, min, root.val) && rec(root.right, root.val,
max);
}
}
但现在OJ加了新的test case，会有
Input: {2147483647}
Output: false
Expected: true
到达极端min，max时，判定条件就不适用了
这样的话程序该怎么改啊？
谢谢指教！ | w*****t
发帖数: 485 | 2 将int max, int min 改成指针:
int *max, int *min
初始的时候都为null, 表示上下界
java的话应该也可以用null | s******3
发帖数: 61 | 3 不懂啊，
能否展开讲讲？
java下怎么用？
【在 w*****t 的大作中提到】
: 将int max, int min 改成指针:
: int *max, int *min
: 初始的时候都为null, 表示上下界
: java的话应该也可以用null
| g*****g
发帖数: 34805 | 4 You can setup boolean instance variable to mark if Integer.MIN and MAX are
taken.
if(taken && equals) => false | T******e
发帖数: 157 | | y*****e
发帖数: 712 | 6 这题是我面groupon的店面题，所以印象深刻。。
有两个写法，一个是5楼说的，记录前一个值，比较是不是一直在变大。我和你是一样
的写法，都是比较左右两个叶子。对于max和min两个test case，最简单的还是直接拿
出来判断一下
public boolean validate(TreeNode root){
if(root == null)
return true;
return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean helper(TreeNode root, int low, int high){
if(root == null)
return true;
if(root.val == Integer.MIN_VALUE && root.left != null)
return false;
if(root.val == Integer.MAX_VALUE && root.right != null)
return false;
if(low <= root.val && root.val <= high){
return helper(root.left, low, root.val - 1) && helper(root.right,
root.val + 1, high);
}
return false;
} | x********k
发帖数: 256 | 7 java 下的函数可以用isValidBSTRecur(TreeNode root, Integer min, Integer max)
然后你就可以用
if (min != null && root.val <= min) return false;
if (max != null && root.val >= max) return false;
这样的判断了。
调用时也是可以用null值isValidBSTRecur(root,null,null);
【在 s******3 的大作中提到】
: 不懂啊，
: 能否展开讲讲？
: java下怎么用？
|
|
