【力扣题解】P98-验证二叉搜索树-Java题解

花无缺

👨‍💻博客主页：@花无缺
欢迎点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创

收录于专栏【力扣题解】

文章目录

【力扣题解】P98-验证二叉搜索树-Java题解
- 🌏题目描述
- 💡题解
- 🌏总结

【力扣题解】P98-验证二叉搜索树-Java题解

P98.验证二叉搜索树

🌏题目描述

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

有效二叉搜索树定义如下：

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

示例 1：

在这里插入图片描述

输入：root = [2,1,3]
输出：true

示例 2：

在这里插入图片描述

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

💡题解

递归法1：

// list 保存中序序列
List<Long> list = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
    // 中序遍历二叉树, 将中序序列保存到 list 中
    dfs(root);
    // 遍历 list, 如果 list 是一个递增的序列, 那么这就是一棵二叉搜索树
    for (int i = 0; i < list.size() - 1; i++) {
        if (list.get(i) >= list.get(i + 1)) {
            return false;
        }
    }
    return true;
}
public void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    // 中序遍历, 将节点值放入 list
    list.add((long) root.val);
    dfs(root.right);
}

递归法2：

// pre 保存上一个遍历的节点值
long pre = Long.MIN_VALUE;
public boolean isValidBST2(TreeNode root) {
    // 空树也是二叉搜索树
    if (root == null) {
        return true;
    }
    // 递归判断左子树
    boolean left = isValidBST2(root.left);
    // 如果当前节点的值大于上一个遍历的节点值那么就是符合二叉搜索树的
    // 继续遍历
    if (root.val > pre) {
        pre = root.val;
    //     如果当前节点的值小于等于上一个遍历的节点值, 那么该树就不是二叉搜索树
    } else {
        return false;
    }
    // 递归判断右子树
    boolean right = isValidBST2(root.right);
    // 左右子树都是二叉搜索树
    return left && right;
}

时间复杂度均为O(n)，需要遍历二叉树的所有节点，二叉树节点数为 n。

🌏总结

我们知道二叉搜索树的左子树的所有节点值一定小于根节点，右子树的所有节点值一定大于根节点，并且所有子树都是二叉搜索树，根据二叉树的这个特性，我们可以推出，二叉搜索树的中序序列一定是一个由小到大排列的递增序列，所以我们可以对树进行中序遍历，然后判断这个序列是否是严格递增的，如果是那么就是二叉搜索树，如果不是那么就不是二叉搜索树。

递归1解法就是采用这个思路的，将中序遍历序列放入列表 list 中，然后判断 list 是否递增。而递归2解法可以不使用列表，而是直接在递归的时候判断当前节点是否大于上一个遍历过的节点，如果递归结束所有节点都满足那么就是二叉搜索树，只要有一个节点是小于等于上一个节点的，那么就不是二叉搜索树。另外，要注意 pre 的初始值要比 int 的最小值小，因为题目的节点值数据范围是整个 int 范围，所以我们直接将 pre 设置为 long 类型数据，并初始化为 long 的最小值。

作者：花无缺(huawuque404.com)