// @Title: 验证二叉搜索树 (Validate Binary Search Tree)
// @Author: qisiii
// @Date: 2024-09-16 01:50:22
// @Runtime: 2 ms
// @Memory: 42.4 MB
// @comment: 也是递归但效率不高，是用root和子树的所有节点去比较了
// @flag: WHITE
/**
 * 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||(root.left==null&&root.right==null)){
            return true;
        }
        if(!isValidBST(root.left)||!isValidBST(root.right)){
            return false;
        }
        if(!valid(root.val,root.left,true)||!valid(root.val,root.right,false)){
            return false;
        }
        return true;
    }

    private boolean valid(int val,TreeNode node,boolean max){
        if(node==null){
            return true;
        }
        if(max){
           return val>node.val&&valid(val,node.left,max)&&valid(val,node.right,max);
        }else{
            return val<node.val&&valid(val,node.left,max)&&valid(val,node.right,max);
        }
    }
}

// @Title: 验证二叉搜索树 (Validate Binary Search Tree)
// @Author: qisiii
// @Date: 2024-09-16 02:24:43
// @Runtime: 0 ms
// @Memory: 43.4 MB
// @comment: 官方题解的递归，由上到下，缩小区间，节点只需要和区间比较即可
// @flag: WHITE
/**
 * 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 isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode node,Long min,Long max){
        if(node==null){
            return true;
        }
        if(node.val<=min||node.val>=max){
            return false;
        }
        return isValidBST(node.left,min,Long.valueOf(node.val))&&isValidBST(node.right,Long.valueOf(node.val),max);
    }
}