98.验证二叉搜索树

比眉伴天荒 2023-10-16 11:05 11阅读 0赞

#### 98.验证二叉搜索树 ####

*  题目描述
 *  解题思路
 *   *  递归法
     *   *  容易调入的陷阱
         *   *  陷阱1
             *  陷阱2
             *  递归三部曲
             *   *  确定递归函数，返回值以及参数
                 *  确定终止条件
                 *  确定单层递归的逻辑
     *  迭代法
 *  代码实现
 *   *  使用统一迭代法
     *  递归法
     *  迭代法
     *  简洁实现递归解法
     *  简洁实现中序遍历

## 题目描述 ##

[98.验证二叉搜索树-力扣入口][98._-]

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。  
节点的右子树只包含大于当前节点的数。  
所有左子树和右子树自身必须也是二叉搜索树。

![在这里插入图片描述][d584ecbff0e9490cb76a023a66b128a2.png]

## 解题思路 ##

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，**验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了**。

### 递归法 ###

可以递归中序遍历将二叉搜索树转变成一个数组。

然后只要比较一下，这个数组是否是有序的，**注意二叉搜索树中不能有重复元素**。

其实也可以不用转变成数组，可以在递归遍历的过程中直接判断是否有序。

#### 容易调入的陷阱 ####

##### 陷阱1 #####

不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。

我们要比较的是 左子树**所有**节点小于中间节点，右子树**所有**节点大于中间节点。

如图所示：  
![在这里插入图片描述][c4cf3e341f0540ba905d71a6b9edecca.png]  
节点10大于左节点5，小于右节点15，但右子树里出现了一个6 这就不符合了！

##### 陷阱2 #####

样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。

此时可以初始化比较元素为longlong的最小值。

##### 递归三部曲 #####

###### 确定递归函数，返回值以及参数 ######

要定义一个longlong的全局变量，用来比较遍历的节点是否有序，因为后台测试数据中int最小值，所以定义为longlong的类型，初始化为longlong最小值。

注意递归函数要有bool类型的返回值，只有寻找某一条边（或者一个节点）的时候，递归函数会有bool类型的返回值。

我们在寻找一个不符合条件的节点，如果没有找到这个节点就遍历了整个树，如果找到不符合的节点了，立刻返回。

long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值
    bool isValidBST(TreeNode* root);

###### 确定终止条件 ######

如果是空节点 是不是二叉搜索树呢？

是的，二叉搜索树也可以为空！

代码如下：

if(root == NULL) return true;

###### 确定单层递归的逻辑 ######

中序遍历，一直更新maxVal，一旦发现maxVal大于root的值，就返回false。注意元素相同时候也要返回false。

如果测试数据中有longlong的最小值，怎么办？  
不可能再初始化一个更小的值了，可取到最左面节点的数值来比较。

### 迭代法 ###

迭代法中序遍历稍加改动就可以了。

## 代码实现 ##

### 使用统一迭代法 ###

// 98.验证二叉搜索树 - 使用统一迭代法
    public boolean isValidBST(TreeNode root){
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        if(root != null)
            stack.add(root);
        while(!stack.isEmpty()){
        
            TreeNode curr = stack.peek();
            if(curr != null){
        
                stack.pop();
                if(curr.right != null)
                    stack.add(curr.right);
                stack.add(curr);
                stack.add(null);
                if(curr.left != null)
                    stack.add(curr.left);
            }else{
        
                stack.pop();
                TreeNode temp = stack.pop();
                if(pre != null && pre.val >= temp.val)
                    return false;
                pre = temp;
            }
        }
        return true;
    }

### 递归法 ###

// 98.验证二叉搜索树 - 递归法
    TreeNode max;
    public boolean isValidBST(TreeNode root){
        
        if(root == null){
        
            return true;
        }
        // 左
        boolean left = isValidBST(root.left);
        if(!left){
        
            return false;
        }
        // 中
        if(max != null && root.val <= max.val){
        
            return false;
        }
        max = root;
        // 右
        boolean right = isValidBST(root.right);
        return right;
    }

### 迭代法 ###

// 98.验证二叉搜索树 - 迭代
    public boolean isValidBST(TreeNode root){
        
        if(root == null){
        
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while(root != null || !stack.isEmpty()){
        
            while(root != null){
        
                stack.push(root);
                root = root.left; // 左
            }
            // 中，处理
            TreeNode pop = stack.pop();
            if(pre != null && pop.val <= pre.val){
        
                return false;
            }
            pre = pop;
    
            root = pop.right; // 右
        }
        return true;
    }

### 简洁实现递归解法 ###

// 98.验证二叉搜索树 - 简洁实现递归解法
    public boolean isValidBST(TreeNode root){
        
        return validBST(Long.MIN_VALUE, Long.MAX_VALUE, root);
    }
    boolean validBST(long lower, long upper, TreeNode root){
        
        if(root == null) return true;
        if(root.val <= lower || root.val >= upper) return false;
        return validBST(lower, root.val, root.left) && validBST(root.val, upper, root.right);
    }

### 简洁实现中序遍历 ###

// 98.验证二叉搜索树 - 简洁实现中序遍历
    private 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);
    }

**参考资料**：[代码随想录-98.验证二叉搜索树][-98.]

[98._-]: https://leetcode.cn/problems/validate-binary-search-tree/
[d584ecbff0e9490cb76a023a66b128a2.png]: https://img-blog.csdnimg.cn/d584ecbff0e9490cb76a023a66b128a2.png
[c4cf3e341f0540ba905d71a6b9edecca.png]: https://img-blog.csdnimg.cn/c4cf3e341f0540ba905d71a6b9edecca.png
[-98.]: https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE