- Validate Binary Search Tree:题目链接
递归解法
错误的解法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
// 递归宏观语义:返回以root为根节点的二叉树是不是二分搜索树
// 此写法错误
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if ((root.left != null && root.val <= root.left.val) || (root.right != null && root.val >= root.right.val)) {
return false;
}
return isValidBST(root.left) && isValidBST(root.right);
}
}
修改后的解法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, null, null);
}
// 递归宏观语义:返回以root为根节点的二叉树是不是二分搜索树 当前结点.val ∈ (leftLimit,rightLimit)
public boolean helper(TreeNode root, Integer leftLimit, Integer rightLimit ) {
if (root == null) {
return true;
}
if ((leftLimit != null && root.val <= leftLimit) || (rightLimit != null && root.val >= rightLimit)) {
return false;
}
return helper(root.left, leftLimit, root.val) && helper(root.right, root.val, rightLimit);
}
}