当前位置 博文首页 > Yawn：Leetcode——验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
错误题解：
最容易想到的：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
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);
}
}
如果遇到下面的情况，就会产生误判：
注意6这个节点不光要小于15而且还要大于10，所以这里的每一个节点都是有一个范围的，上面的代码我只判断了6比15小，但没有和10进行比较，所以代码是错误的。
正确题解： 递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return help(root, Long.MIN_VALUE, Long.MAX_VALUE);
//为什么用Integer会报错？
//因为当该树只有一个结点值为 Integer.MIN_VALUE或Integer.MAX_VALUE时，
//在进行递归的时候，就会进入第二个if判断，返回false，但是其实应该为true的，要考虑到这一种情况。
//这里只能用Long类型，因为树是int类型，用Integer可能会被覆盖。
}
public boolean help(TreeNode node, long min, long max){
//下面只能用long
if(node == null)
return true;
if(node.val >= max || node.val <= min)
return false;
return help(node.left, min, node.val) && help(node.right, node.val, max);
//注意这句，控制边界值，防止上面发生的情况
}
}
//或者这样也可以！
/*------------------------------------------------------------------------------------*/
class Solution {
public boolean isValidBST(TreeNode root) {
return help(root, null, null);
}
public boolean help(TreeNode node, TreeNode min, TreeNode max){
if(node == null)
return true;
if(min != null && node.val <= min.val)
return false;
if(max != null && node.val >= max.val)
return false;
return help(node.left, min, node) && help(node.right, node, max);
}
}
正确题解： 迭代
遍历结果为：123456
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<TreeNode>(); //注意：这里是实现栈
long inorder = Long.MIN_VALUE;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
// Deque用作栈，先进后出（用于取出前一个节点用作比较）
// 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
if (root.val <= inorder) {
return false;
}
inorder = root.val;
root = root.right;
}
return true;
}
}
