LeetCode 98：验证二叉搜索树（Validate Binary Search Tree）题解

Validate Binary Search Tree 是 LeetCode Hot 100 里面一道非常经典的二叉树题。

这道题表面上看起来不难，因为题目只是让我们判断一棵树是不是二叉搜索树。 但它真正容易出错的地方在于：

很多人会只盯着“当前节点和左右孩子比较大小”，却忽略了二叉搜索树的定义其实是对整棵子树都生效的。

这也是这题最经典的坑点。

你给出的这份 Java 代码，使用的是这道题非常标准、也非常推荐的一种写法：

递归 + 上下界约束

这种解法的核心思想非常清晰：

• 对于任意一个节点，它不仅要比左孩子大、比右孩子小

• 更重要的是，它必须落在某个合法区间 (lower, upper) 内

• 左子树递归时更新上界

• 右子树递归时更新下界

本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给你一棵二叉树的根节点 root，要求你判断它是否是一棵有效的二叉搜索树。

二叉搜索树（BST）的定义是：

1. 节点的左子树只包含 小于 当前节点的数

2. 节点的右子树只包含 大于 当前节点的数

3. 左右子树本身也必须都是二叉搜索树

注意这里有两个非常关键的词：

• 严格小于

• 严格大于

也就是说，不能出现相等的情况。

例如下面这棵树：

    2
   / \
  1   3

它是一棵合法的 BST。

但如果是：

    5
   / \
  1   4
     / \
    3   6

它就不是一棵合法的 BST。 因为右子树中的节点 3 虽然小于 4，但它其实也必须大于根节点 5，这一点不满足。

这正是这道题最容易误判的地方。

示例

示例 1

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

因为：

• 左子节点 1 < 2

• 右子节点 3 > 2

• 且左右子树本身也都满足 BST 条件

所以答案是 true。

示例 2

输入：root = [5,1,4,null,null,3,6]
输出：false

因为节点 3 虽然位于节点 4 的左侧，但它其实属于根节点 5 的右子树。 在右子树里，所有节点都必须大于 5，而 3 < 5，所以这棵树不是合法 BST。

为什么这道题容易写错？

很多人第一次做这题时，会下意识写成这样：

• 当前节点要比左孩子大

• 当前节点要比右孩子小

• 然后递归检查左右子树

看起来很合理，但其实这个判断是不够的。

因为 BST 的约束不是只看“父子关系”，而是看：

整棵左子树都要小于当前节点，整棵右子树都要大于当前节点。

例如这棵树：

    5
   / \
  4   6
     / \
    3   7

如果你只检查父子关系，会发现：

• 4 < 5

• 6 > 5

• 3 < 6

• 7 > 6

看起来都没问题。

但实际上 3 位于根节点 5 的右子树中，所以它也必须满足：

3 > 5

显然不成立。

这说明：

只比较当前节点和直接孩子是不够的，必须把祖先节点带来的限制一起传下去。

这就是上下界写法的本质。

核心思路：递归维护合法区间

对于任意一个节点，我们都可以给它规定一个允许取值的区间：

(lower, upper)

含义是：

• 当前节点的值必须严格大于 lower

• 严格小于 upper

初始情况

根节点一开始没有任何约束，所以区间可以设成：

(-∞, +∞)

在代码里用：

Long.MIN_VALUE, Long.MAX_VALUE

来表示。

递归到左子树

因为左子树所有节点都必须小于当前节点，所以左子树递归时：

• 下界不变

• 上界更新成当前节点值

也就是：

(lower, root.val)

递归到右子树

因为右子树所有节点都必须大于当前节点，所以右子树递归时：

• 下界更新成当前节点值

• 上界不变

也就是：

(root.val, upper)

只要在递归过程中，每个节点都满足自己对应的区间约束，那么整棵树就是合法 BST。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

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

    public boolean isValidBST(TreeNode root, long lower, long upper) {
        if (root == null) return true;

        // 当前节点不在合法区间内，直接返回 false
        if (root.val <= lower || root.val >= upper) return false;

        // 左子树的上界是当前节点值
        // 右子树的下界是当前节点值
        return isValidBST(root.left, lower, root.val)
            && isValidBST(root.right, root.val, upper);
    }
}

代码拆解

这段代码不长，但它几乎就是这道题最标准的模板写法。 下面一步一步来看。

1. 为什么主函数要调用带边界的递归函数？

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

因为根节点一开始没有来自祖先的限制。 所以它的合法范围可以看成：

(-∞, +∞)

在代码里，用：

• Long.MIN_VALUE 表示极小下界

• Long.MAX_VALUE 表示极大上界

然后从这个最宽松的区间开始递归检查整棵树。

2. 为什么空节点返回 true？

if (root == null) return true;

因为空树本身是合法的二叉搜索树。

而且从递归角度看，空节点意味着：

• 当前这条分支已经检查到头了

• 没有发现违反规则的地方

所以应当返回 true。

这是二叉树递归题里非常常见的边界条件。

3. 为什么当前节点要检查是否在 (lower, upper) 区间内？

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

因为当前节点不仅受到父节点影响，还受到整条祖先路径带下来的限制。

举个例子：

    5
     \
      8
     /
    6

对于节点 6 来说：

• 它确实小于父节点 8

• 但它也必须大于祖先节点 5

所以它的合法区间其实是：

(5, 8)

这就是为什么我们不能只和父节点比，而要维护整个区间。

另外这里用的是：

<= lower || >= upper

而不是：

< lower || > upper

因为 BST 要求是严格小于、严格大于，所以边界不能取等号。

4. 为什么左子树递归时要把上界改成 root.val？

isValidBST(root.left, lower, root.val)

因为左子树所有节点都必须严格小于当前节点值。

所以对左子树来说：

• 原来的下界 lower 继续保留

• 新的上界变成 root.val

这样左子树中的所有节点都会自动被约束在：

(lower, root.val)

这个范围里。

5. 为什么右子树递归时要把下界改成 root.val？

isValidBST(root.right, root.val, upper)

同理，右子树所有节点都必须严格大于当前节点值。

所以对右子树来说：

• 新的下界变成 root.val

• 原来的上界 upper 保留

于是右子树中的所有节点都被限制在：

(root.val, upper)

这个范围内。

6. 为什么要用 long，而不是 int？

Long.MIN_VALUE, Long.MAX_VALUE

这是一个非常重要的细节。

因为题目中的节点值本身是 int。 如果你也用 int 来做边界，那么当节点值刚好等于：

Integer.MIN_VALUE

或者：

Integer.MAX_VALUE

时，就容易出问题。

例如，如果根节点值就是 Integer.MIN_VALUE，而你把初始下界也设成 Integer.MIN_VALUE，那么：

root.val <= lower

就会误判。

所以这里用更大的 long 类型做边界，能把这个问题彻底规避掉。

这是这道题一个非常经典的实现细节。

手动模拟一遍

我们用经典反例来走一遍：

    5
   / \
  1   4
     / \
    3   6

第一步：检查根节点 5

初始区间：

(-∞, +∞)

节点 5 满足要求。

• 左子树区间变成：(-∞, 5)

• 右子树区间变成：(5, +∞)

第二步：检查左子节点 1

区间：

(-∞, 5)

1 落在区间内，所以合法。

第三步：检查右子节点 4

区间：

(5, +∞)

但此时：

4 <= 5

不满足区间要求，所以立即返回 false。

这样整棵树也就被判断为不是合法 BST。

这正是这道题的关键： 虽然 4 是根节点 5 的右孩子，看起来只要大于 5 就行，但它自己本身已经不满足要求，更不用说它下面还有个 3 了。

为什么这个方法是正确的？

因为 BST 的定义本质上就是：

• 每个节点都必须落在一个由祖先节点共同决定的合法区间内

这个区间递归传递的规则是：

• 去左子树时，更新上界

• 去右子树时，更新下界

只要在递归过程中：

• 每个节点都满足自己的合法区间

• 左右子树也都递归满足

那么整棵树一定是合法 BST。

反过来，只要有任意一个节点超出了它应该处于的范围，就说明它违反了某个祖先节点对它的约束，那这棵树就不可能是合法 BST。

因此这个方法是完全正确的。

复杂度分析

假设二叉树一共有 n 个节点。

时间复杂度

每个节点都只会被访问一次，所以时间复杂度是：

O(n)

空间复杂度

额外空间主要来自递归调用栈。

最坏情况下，如果树退化成链表，递归深度为 n，所以空间复杂度是：

O(n)

如果树比较平衡，递归深度大约是树高：

O(log n)

但通常写最坏情况为 O(n)。

这道题真正想考什么？

这道题表面上是在判断 BST，但本质上考察的是二叉树递归中的“全局约束”思想。

第一，能不能意识到“只比较父子节点是不够的”

这是这道题最核心的坑点。 如果只会检查：

• root.left.val < root.val

• root.right.val > root.val

那一定会被反例卡住。

第二，能不能把祖先约束通过递归传下去

这道题真正高明的地方在于：

• 不是向下传一个值

• 而是向下传一个区间

这是一种非常典型的递归设计方式。

第三，是否注意边界类型要用 long

这是实现层面最容易忽略、但非常经典的细节。

这题还有别的写法吗？

有。

除了“上下界递归”写法之外，这题还有一个非常经典的思路：

利用中序遍历

因为二叉搜索树的中序遍历结果一定是严格递增的。 所以只要做一次中序遍历，检查遍历序列是不是严格递增，也能判断它是不是 BST。

这也是很常见的一种解法。

不过从逻辑直观程度上来说，你现在这份“上下界递归”写法其实非常干净，也非常适合作为博客主解法，因为它最直接地体现了 BST 的定义。

和“二叉树的中序遍历”有什么联系？

前一题你写的是“中序遍历”，而这题恰好和中序遍历也有深层联系：

• 普通二叉树中序遍历只是按顺序访问节点

• 如果一棵树是 BST，那么它的中序遍历结果会严格递增

所以从某种意义上说：

这道题也可以看成是在利用 BST 的中序有序性质。

但相比之下，你现在这份“区间限制”写法更贴近 BST 定义本身。

总结

这道题的核心思想可以概括成一句话：

判断一棵树是不是合法 BST，不能只比较当前节点和左右孩子，而是要保证每个节点都落在由所有祖先共同确定的合法区间内。

具体做法就是：

1. 从根节点开始，初始合法范围设为 (-∞, +∞)

2. 如果当前节点值不在 (lower, upper) 区间内，直接返回 false

3. 递归检查左子树时，把当前节点值作为新的上界

4. 递归检查右子树时，把当前节点值作为新的下界

5. 只有左右子树都合法，当前树才合法

这样就能在线性时间内完成判断。

这是一道非常经典、也非常值得认真理解的二叉树题。 因为它会让你真正体会到：

• 局部条件和全局条件的区别

• 树递归中“向下传约束”的思维方式

• 为什么同一个题目可以从定义本身和遍历性质两个角度去解

把这道题真正吃透之后，再去看：

• 二叉搜索树中的搜索

• 恢复二叉搜索树

• 删除二叉搜索树中的节点

• 有序数组转 BST

这些 BST 题时，你会更容易抓住它们背后的共同规律。

因为“验证二叉搜索树”本身就是 BST 基础题里最经典的一道模板题。