二叉树问题——验证二叉搜索树

摘要

98. 验证二叉搜索树‘

一、验证二叉搜索树解析

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：

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

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

1.1 暴力方法(中序遍历)

1.1.1 思路解析

1.1.2 代码解析

package Tree;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Tree
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-26  23:49
 * @Description: TODO
 * @Version: 1.0
 */
public class 二叉搜索树的验证98 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
 
        TreeNode() {
        }
 
        TreeNode(int val) {
            this.val = val;
        }
 
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
 
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        List list = new ArrayList<>();
        dfs(root, list);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) < list.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
 
    private void dfs(TreeNode root, List list) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            dfs(root.left, list);
        }
        list.add(root.val);
        if (root.right != null) {
            dfs(root.right, list);
        }
    }
}

1.1.3 复杂度分析

• 时间复杂度为：O(N)
• 空间复杂度为:O(N) 利用一个数组来存储二叉树的中元素

1.2 利用变量存储前一个位置的值

1.2.1 思路图解

 1.2.2 代码解析

package Tree;
 
/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Tree
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-26  23:49
 * @Description: TODO
 * @Version: 1.0
 */
public class 二叉搜索树的验证98 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
 
        TreeNode() {
        }
 
        TreeNode(int val) {
            this.val = val;
        }
 
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    // 采用中序遍历来实现 空间需要o(N) 时间为O(N)
    //
    long maxvalue=Long.MIN_VALUE;
 
    public boolean isValidBST(TreeNode root) {
        if (root==null){
            return true;
        }
        // 左
        boolean left=isValidBST(root.left);
        // 中
        if (root.val>maxvalue){
            maxvalue=root.val;
        }else {
            return false;
        }
        // 右
        boolean right=isValidBST(root.right);
        return left&&right;
    }
}

 1.2.3 复杂度分析

• 时间复杂度为：O(N)
• 空间复杂度为:O(1)

1.3 利用指针存储前一个位置值

1.3.1 思路图解

1.3.2 代码解析

package Tree;
 
/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Tree
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-26  23:49
 * @Description: TODO
 * @Version: 1.0
 */
public class 二叉搜索树的验证98 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
 
        TreeNode() {
        }
 
        TreeNode(int val) {
            this.val = val;
        }
 
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
 
 
    // 采用双指针的方式来实现
    TreeNode pre;
    public boolean isValidBST2(TreeNode root) {
        if (root==null){
            return true;
        }
        // 左
        boolean left=isValidBST(root.left);
        // 中
        if (pre!=null&&pre.val>=root.val){
            return false;
        }
        pre=root;
        // 右
        boolean right=isValidBST(root.right);
        return left&&right;
    }
}

  1.3.3 复杂度分析

• 时间复杂度为：O(N)
• 空间复杂度为:O(1)

二、类似问题

701. 二叉搜索树中的插入操作

669. 修剪二叉搜索树

450. 删除二叉搜索树中的节点

230. 二叉搜索树中第K小的元素

235. 二叉搜索树的最近公共祖先

783. 二叉搜索树节点最小距离

538. 把二叉搜索树转换为累加树

1038. 从二叉搜索树到更大和树

173. 二叉搜索树迭代器

94. 二叉树的中序遍历

501. 二叉搜索树中的众数

博文参考

《leetcode》