Hot 100 --- 验证二叉搜索树

本文概览：本文以LeetCode题目"验证二叉搜索树"为例，讲解BST的核心性质和两种验证方法：中序遍历（判断递增）和递归上下限传递，重点详解递归中上下限的传递关系

---

一、题目

二、题目分析

二叉搜索树（BST）有一个核心性质：左子树的所有值必须小于根节点的值，右子树的所有值必须大于根节点的值。注意是"所有"，不是"左孩子小于根"就够了

比如下面这棵树就不是合法的 BST：

  5
 / \
4   6
   / \
  3   7

节点 6 的左孩子是 3，3 < 6 没问题，但 3 < 5 吗？3 在根节点 5 的右子树中，右子树的所有值都必须大于 5，而 3 不满足，所以这不是 BST

难点就在于这个"全量判断"——不仅要保证当前节点和直接父节点的关系，还要保证它和更上层祖先节点的关系。这导致递归条件不好找

这题有两种解法：

1. 中序遍历：BST 的中序遍历一定是严格递增的，遍历出来检查即可
2. 递归上下限传递：每个节点维护一个取值范围（上限和下限），递归时向子树传递并缩小范围

思路概览

方法一：中序遍历

class Solution {
    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);
    }
}

方法二：递归上下限传递

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

    private boolean isValidBST(TreeNode node, long lower, long upper) {
        // 递归出口
        if (node == null) return true;
        // 当前节点必须在 (lower, upper) 范围内
        if (node.val <= lower || node.val >= upper) return false;
        // 左子树：上限更新为当前节点值，下限复用
        // 右子树：下限更新为当前节点值，上限复用
        return isValidBST(node.left, lower, node.val)
            && isValidBST(node.right, node.val, upper);
    }
}

思路简要说明

• 方法一：利用 BST 中序遍历严格递增的性质，遍历时维护前一个值 prev，一旦出现 当前值 <= prev 就不是 BST
• 方法二：每个节点都有一个取值范围 (lower, upper)，递归时把范围往子树传递——左子树的上限缩小为当前节点值，右子树的下限缩小为当前节点值

三、思路详解

方法一：中序遍历

BST 有一个重要性质：中序遍历的结果一定是严格递增的

因为在 BST 中，中序遍历的顺序是"左→根→右"，而左子树所有值 < 根 < 右子树所有值，所以遍历出来的序列天然是递增的。如果中途出现非递增，就说明不是 BST

代码就是在中序遍历的基础上加一个判断：用 prev 记录前一个遍历到的值，如果当前值 <= prev，直接返回 false

注意 prev 用 long 类型且初始值为 Long.MIN_VALUE，是为了处理节点值为 Integer.MIN_VALUE 的边界情况

方法二：递归上下限传递（重点）

为什么直接递归不好写？

如果按"左根右"整体来看，递归出口很难找——你需要同时保证左子树所有值 < 根，右子树所有值 > 根，而且这个约束还会往更深层传递。比如根的右子树中某个节点，它不仅要大于自己的父节点，还要大于根节点。这种"跨层约束"让人很难一次性想清楚

关键转变：不要看整体，看单个节点

二叉树的递归，核心就是看一个节点。如果我们给每个节点划定一个取值范围，只检查当前节点是否在这个范围内，问题就简单了

上下限的含义

每个节点都有一个取值范围 (lower, upper)：

• lower（下限）：当前节点必须大于这个值
• upper（上限）：当前节点必须小于这个值

根节点没有约束，所以初始范围是 (Long.MIN_VALUE, Long.MAX_VALUE)

上下限怎么传递？

核心规则就两条：

• 往左子树递：上限更新为当前节点值，下限复用当前节点的下限
• 往右子树递：下限更新为当前节点值，上限复用当前节点的上限

为什么？先看第一轮：

        5
       / \
      3   6

根节点5的范围：(MIN, MAX)
→ 左子树3：必须 < 5，所以上限变为 5，下限没要求，复用 MIN → (MIN, 5)
→ 右子树6：必须 > 5，所以下限变为 5，上限没要求，复用 MAX → (5, MAX)

这一轮很好理解。3 是 5 的左孩子，只需要小于 5；6 是 5 的右孩子，只需要大于 5

关键在下一轮——为什么要"复用"父节点的上下限？看这个例子：

  5
 / \
3   6
   / \
  4   7

节点 6 的范围是 (5, MAX)。现在看 6 的子树：

6 的左孩子 4：

• 4 必须 < 6（因为 4 是 6 的左孩子）→ 上限 = 6
• 4 必须 > 5（因为 4 在 5 的右子树中，右子树所有值 > 5）→ 下限 = 5（复用 6 的下限）
• 所以 4 的范围 = (5, 6)

6 的右孩子 7：

• 7 必须 > 6（因为 7 是 6 的右孩子）→ 下限 = 6
• 7 没有更上的上限约束 → 上限复用 6 的上限 = MAX
• 所以 7 的范围 = (6, MAX)

可以看到，4 的下限 5 不是来自 6，而是来自更上层的根节点 5。这就是"复用"的含义——6 把从祖先那里继承来的下限 5 继续传递给左子树

如果不复用，4 的范围会变成 (6, 6) 或者 (MIN, 6)，那就无法保证 4 > 5，就会漏判

用图把完整传递过程画出来：

            5
           / \
          3   6
             / \
            4   7

各节点的范围 (lower, upper)：

5:  (MIN, MAX)         ← 根节点无约束
3:  (MIN, 5)           ← 左子树：上限=5，下限复用MIN
6:  (5, MAX)           ← 右子树：下限=5，上限复用MAX
4:  (5, 6)             ← 6的左子树：上限=6，下限复用6的下限→5
7:  (6, MAX)           ← 6的右子树：下限=6，上限复用6的上限→MAX

4 的范围是 (5, 6)，意味着 4 必须满足 5 < 4 < 6，而 4 不满足，所以这不是 BST

再看一个更深层的例子，体会复用的作用：

            10
           /  \
          5    15
              /  \
            12    20
           /  \
         11    14
        /
      9           ← 这个9有问题

各节点的范围 (lower, upper)：

10:  (MIN, MAX)
 5:  (MIN, 10)          ← 上限=10，下限复用MIN
15:  (10, MAX)          ← 下限=10，上限复用MAX
12:  (10, 15)           ← 上限=15，下限复用15的下限→10
20:  (15, MAX)          ← 下限=15，上限复用15的上限→MAX
11:  (10, 12)           ← 上限=12，下限复用12的下限→10
14:  (12, 15)           ← 上限=15，下限复用15的... 不对，上限复用12的上限→15
                            下限=12，上限复用12的上限→15
9:   (10, 11)           ← 上限=11，下限复用11的下限→10

9 的范围是 (10, 11)，必须满足 10 < 9 < 11，而 9 < 10，不满足！所以这不是 BST

这就是复用的精髓：9 虽然是 11 的左孩子（9 < 11 没问题），但它同时在 10 的右子树中（必须 > 10），也在 12 的左子树中（必须 < 12），也在 15 的左子树中（必须 < 15）。这些来自祖先的约束，就是通过"复用"一层层传下来的

递归三步分析

回到我们之前讲的递归三步框架：

• 出口：if (node == null) return true; — 空节点不违反任何约束
• 出口补充：if (node.val <= lower || node.val >= upper) return false; — 当前节点超出范围
• 递归调用：
  • 左子树：isValidBST(node.left, lower, node.val) — 上限更新为当前节点值，下限复用
  • 右子树：isValidBST(node.right, node.val, upper) — 下限更新为当前节点值，上限复用

这和之前二叉树递归题的模式完全一样：出口判断 → 递归调用。只不过这里多了一个"上下限传递"的机制

为什么用 long 不用 int？

因为节点值的范围是 Integer.MIN_VALUE 到 Integer.MAX_VALUE。如果用 int 类型的上下限，当节点值恰好等于 Integer.MIN_VALUE 或 Integer.MAX_VALUE 时，就无法区分"边界值"和"无约束"。用 long 并初始化为 Long.MIN_VALUE 和 Long.MAX_VALUE，就不会有这个问题

两种方法对比

	中序遍历	递归上下限传递
思路	利用BST中序递增性质	给每个节点维护取值范围
额外空间	O(1)（只需prev变量）	O(1)（参数传递）
递归结构	中序遍历框架	后序/先序都行
理解难度	较低	较高（上下限传递关系）

两种方法时间复杂度都是 O(n)，空间复杂度都是 O(h)（h 为树高，递归栈开销）

中序遍历更直观，但递归上下限传递的思想更通用——它体现了"把全局约束分解为局部约束"的思路，在很多涉及区间判断的题目中都会用到