8.验证二叉搜索树

• 2.11
  • 最小值应该为 long 类型，思路秒了

class Solution {
    long current = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        if(!isValidBST(root.left)) return false;
        if(root.val<=current){
            return false;
        }else{
            current = root.val;
            return  isValidBST(root.right);
        }
    }
}

• 1.26

  • 第二种方法更简单，但需要注意最小一个为 long 类型的最小值

• 1.16

  • 找到宝藏了，刚开始的思路有问题

    • 之前是递归比较左右子树节点大小，是局部的
    • 正确的思路是维护全局左右边界值，带资入组（long 类型）

  • 跟对称树思路差不多，在比较后，不能 else 返回真，因为目前是局部的，需要整体都为真才能返回真

    • 第二种思路：把严格二叉搜索压扁成递增数组，用 pre 当做前指针从大往小递归，也很精彩 ​-

class Solution {
    public boolean isValidBST(TreeNode root) {
        // if(root.right==null||root.left==null) return false;
        // if(root.left.val>=root.right.val) return false;
 
        // boolean res1 = isValidBST(root.left);
        // boolean res2 =  isValidBST(root.right);
        // return res1&&res2;
        long min = Long.MIN_VALUE;
        long max = Long.MAX_VALUE;
        return check(root,min,max);
        
    }
    public boolean check(TreeNode root,long min,long max){
        if(root==null) return true;
 
        if(root.val<=min||root.val>=max){
            return false;
        }
        return check(root.left,min,root.val)&&check(root.right,root.val,max);
    }
}

11.11 - 声明一个最小数pre这里为long,因为题目范围暗示了 - 算是一个失衡递归,pre是上个节点,所以失衡到底时影判断为root严格>pre才返回true,否则返回false - if(root.val <= prev) return false;错误时才退出递归,不能反方向,因为返回true会提前返回中断递归

class Solution {
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        if(!isValidBST(root.left)) return false;
        if(root.val <= prev) return false;
        prev = root.val;
        return isValidBST(root.right);
    }
}

• 其实没那么难,就是用一个pre来记录上一个root节点
• 其中,pre为long型,默认最小值