/*
1. 判断当前节点是否合法并且递归判断左右子树是否合法
2. 如果root合法，左子树值的合法范围是开区间（-INF，root.val），右子树为（root.val, INF）
3. testcase：
树的形状： null，左子树null，右子树Null， 随机树； 
val的值： 0， -INF， INF， 随机数
*/

/**
 * 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) {
        return isValidBST(root, null, null);
        // null 代表极值，直接用int-max会被特判掉
        // return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    // public boolean isValidBST(TreeNode root, int lower, int upper){
    public boolean isValidBST(TreeNode root, Integer lower, Integer upper){
        if (root == null) return true;
        // if (root.val <= lower || root.val >= upper) return false;
        if (upper != null && root.val >= upper) return false;
        if (lower != null && root.val <= lower) return false;

        // 传入到一下层去判断了, 当前应该只判断本层节点
        // 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, lower, root.val) && isValidBST(root.right, root.val, upper);
    }
}


/**
1. 子树是从左儿子到其叶子的所有节点, 所以需要维护上下界去判断合法性
1.1 搜索顺序: 当前点合法并且 搜索左右子树都合法 
1.2 搜索状态: root, lower, upper
1.3 剪枝: root == null -> true , !( lower < val < upper) -> false

2. 坑爹的边界问题, 记得用LongLong
*/

/**
 * 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) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode root, long lower, long upper){
        if (root == null) return true;
        if (root.val <= lower || upper <= root.val) return false;
        return isValidBST(root.left, lower, Math.min(upper, root.val)) && isValidBST(root.right, Math.max(lower, root.val), upper);
    }
}