98 验证二叉搜索树

一、题目

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

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

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

二、题解

方法一：递归上下界

思路：DFS / 递归 / 二叉搜索树性质

1. 核心思路

这道题不能只判断：root.left.val < root.val < root.right.val

因为二叉搜索树要求的是：

  • 当前节点的整个左子树都必须小于当前节点；
  • 当前节点的整个右子树都必须大于当前节点；
  • 左右子树本身也必须是二叉搜索树。

所以我们可以给每个节点设置一个合法范围：lower < root.val < upper

对于当前节点：

  • 如果进入左子树，那么左子树所有节点都必须小于当前节点；
  • 如果进入右子树，那么右子树所有节点都必须大于当前节点。

2. 具体步骤

  1. 从根节点开始，初始范围是 Long.MIN_VALUE 到 Long.MAX_VALUE。
  2. 判断当前节点的值是否在合法范围内。
  3. 如果当前节点值不满足范围，直接返回 false。
  4. 递归判断左子树和右子树：
    • 左子树范围变成 (lower, root.val)；
    • 右子树范围变成 (root.val, upper)。
  5. 如果左右子树都合法，返回 true。

3. 关键逻辑

if (root.val <= lower || root.val >= upper) {
    return false;
}

解释：

  • 如果 root.val <= lower，说明当前节点太小，不符合二叉搜索树要求；
  • 如果 root.val >= upper，说明当前节点太大，也不符合要求；
  • 因为二叉搜索树要求严格小于和严格大于，所以这里不能写成 < 或 >。

4. 代码

class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean dfs(TreeNode root, long lower, long upper) {
        // 1. 空树是合法的二叉搜索树
        if (root == null) {
            return true;
        }

        // 2. 当前节点必须严格在 lower 和 upper 之间
        if (root.val <= lower || root.val >= upper) {
            return false;
        }

        // 3. 递归判断左子树和右子树
        // 左子树：所有节点都必须小于 root.val
        // 右子树：所有节点都必须大于 root.val
        return dfs(root.left, lower, root.val)
            && dfs(root.right, root.val, upper);
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点最多只会被访问一次，其中 n 是二叉树中的节点数量。

空间复杂度：O(h)O(h)

说明：递归调用栈的深度取决于树的高度 h。

  • 如果是平衡二叉树，空间复杂度是 O(log⁡n)O(\log n)；
  • 如果是链状二叉树，空间复杂度是 O(n)O(n)。

方法二：中序遍历

思路：DFS / 中序遍历 / 二叉搜索树性质

1. 核心思路

二叉搜索树有一个非常重要的性质：

二叉搜索树的中序遍历结果一定是严格递增的。

中序遍历顺序是：

左子树 -> 当前节点 -> 右子树

对于一棵合法的二叉搜索树，中序遍历得到的结果应该是从小到大的。

例如：

    2
   / \
  1   3

中序遍历结果是：

1, 2, 3

这是严格递增的，所以它是合法的二叉搜索树。

如果中序遍历过程中，发现当前节点的值小于或等于上一个访问的节点值，就说明不是二叉搜索树。

2. 具体步骤

  1. 定义变量 prev，记录中序遍历过程中上一个访问过的节点值。
  2. 先递归遍历左子树。
  3. 判断当前节点值是否大于 prev。
  4. 如果当前节点值小于或等于 prev，返回 false。
  5. 更新 prev 为当前节点值。
  6. 最后递归遍历右子树。
  7. 如果整个遍历过程没有发现问题，返回 true。

3. 关键逻辑

if (root.val <= prev) {
    return false;
}

解释：

  • 中序遍历二叉搜索树时，访问到的节点值必须严格递增；
  • 如果当前节点值 root.val 小于或等于上一个节点值 prev；
  • 说明中序遍历结果不是严格递增的，因此不是合法二叉搜索树。

4. 代码

class Solution {
    // 记录中序遍历时，上一个访问过的节点值
    private long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }

    private boolean inorder(TreeNode root) {
        // 1. 空节点是合法的
        if (root == null) {
            return true;
        }

        // 2. 先判断左子树
        if (!inorder(root.left)) {
            return false;
        }

        // 3. 当前节点必须大于上一个访问过的节点
        if (root.val <= prev) {
            return false;
        }

        // 4. 更新 prev
        prev = root.val;

        // 5. 再判断右子树
        return inorder(root.right);
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：中序遍历会访问每个节点一次，其中 n 是二叉树中的节点数量。

空间复杂度：O(h)O(h)

说明：递归调用栈的深度取决于树的高度 h。

  • 如果是平衡二叉树，空间复杂度是 O(log⁡n)O(\log n)；
  • 如果是链状二叉树，空间复杂度是 O(n)O(n)。

评论