98. Validate Binary Search Tree(验证二叉搜索树)

题目链接：https://leetcode-cn.com/problems/validate-binary-search-tree/

错误的做法：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null)
            return true;
        if(root.left!=null&&root.val<=root.left.val)
            return false;
        if(root.right!=null&&root.val>=root.right.val)
            return false;
        return isValidBST(root.left)&&isValidBST(root.right);
    }
}

这种判断方式忽略了root节点跟叶子节点应当保持的大小关系。

正确的思路应该是，

给每一层递归规定一个大小范围，

root节点的左子树要小于root.val ，右子树大于root.val。

比如：[10,5,15，null，null，6,20]

这里的6<10不符合条件。

AC 0ms 100% java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null)
            return true;
        return helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean helper(TreeNode root,long min,long max){
        if(root==null)
            return true;
        if(root.val>=max||root.val<=min)
            return false;
        return helper(root.left,min,root.val)&&helper(root.right,root.val,max);
    }
}