LeetCode 98：验证二叉搜索树

小半 • 2023年2月3日上午10:53 • 技术随笔 • 阅读 188

LeetCode 98
题目：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

注意：
BST的左子树的所有节点都要小于root，右子树的所有节点都要大于root
BST问题的思路 ①左小右大 ②BST中序遍历为升序排列

方法一：中序性质

BST中序遍历则是升序排列
这里每次只需要比较前一个节点pre是否＜当前root的值即可，直到遍历结束。


class Solution {
    TreeNode pre=null;
    public boolean isValidBST(TreeNode root) {
        // 中序遍历为升序排列

        if(root==null){
            return true;
        }
        if(!isValidBST(root.left)){ //判断左子树是否为BST
            return false;
        }
        // 中序
        if(pre!=null && pre.val>=root.val){ // 如果前一个节点值>=root值，则不满足BST
            return false;
        }  // 否则将root作为pre
        pre=root; // ※※※ 左中右，依次更新pre的值
        return isValidBST(root.right); //判断右子树是否为BST
    }
}

或者使用成员变量来记录结果：


class Solution {
    TreeNode pre=null;
    boolean r=true;
    public boolean isValidBST(TreeNode root) {
        check(root);
        return r;
    }

    void check(TreeNode root){
        if(root==null){
            return;
        }
        //中序
        check(root.left);

        if(pre!=null && pre.val>=root.val){
            r=false;
            return;
        }
        pre=root;
        check(root.right);
    }
}

方法二：左小右大性质

要求：
由BST定义：root大于所有的左子树，root小于所有的右子树

如果单独要求左子树的max和右子树的min会违背 递归函数同等权
每次递归要对所有节点的操作是同等权的
使用辅助函数，在参数中携带额外信息，将这种约束传递给所有节点

递归三部曲：
1.参数root，min，max；返回值boolean
2.终止条件： null也是BST，null则return true
3.先排除false的可能，然后把root传给左结点的max，root传给右节点的min


class Solution {
    public boolean isValidBST(TreeNode root) {
        // 性质1  左子树小于root，右子树大于root
        return check(root,null,null);
    }


    boolean check(TreeNode root,TreeNode min,TreeNode max){
        if(root==null){ // 空节点是BST
            return true;
        }
        // 排除当前root的false情况
        //  root的min由左节点传入，root应该大于min
        if(min!=null && root.val<=min.val) return false; 
        //  root的max由右节点传入，root应小于max
        if(max!=null && root.val>=max.val) return false; 

        boolean left=check(root.left,min,root); // root是左节点的max
        boolean right=check(root.right,root,max);// root是右节点的min
        return left && right;
    }
}