LeetCode-98-验证二叉搜索树

题目

思路

1. 一眼递归，感觉可以像之前做二叉平衡树的思路那样，判断返回的值是否为false即可，有false则一直返回false。
2. 写了一版发现问题了，在于假如每两层都是符合标准的，但是三层就有可能不符合标准，如[5,4,6,null,null,3,7]这个用例。
3. 题解设计的递归函数为
   helper(root, lower, upper)
   表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r)(l,r) 的范围内

代码

    public boolean isValidBST(TreeNode root) {
    
        boolean flag=true;
        if(root.left!=null) flag = isValidDfs(root.left,Long.MIN_VALUE,root.val);
        if(root.right!=null && flag==true) flag = isValidDfs(root.right,root.val,Long.MAX_VALUE);
        return flag;
    }
    //判断以root为根的子树所有节点，是否都在(lower,upper)范围内
    public boolean isValidDfs(TreeNode root,long lower,long upper){
    
        //如果不符合要求 直接返回 不用往下找了
        if(root.val<=lower || root.val>=upper) return false;
        //符合要求 则看其左右子树是否符合要求
        boolean flag=true;
        if(root.left!=null) flag = isValidDfs(root.left,lower,root.val);
        if(root.right!=null && flag==true) flag = isValidDfs(root.right,root.val,upper);
        return flag;
    }