98. 验证二叉搜索树

题目描述

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

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

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

示例 1

text

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

示例 2

text

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

解释

根节点值为 5，但是它的右子树中存在值为 3 的节点，而 3 < 5，所以不是有效的二叉搜索树。

约束

树中节点数目范围在 [1, 10^4] 内
-2^31 <= Node.val <= 2^31 - 1

核心思路

这题最容易犯的错是：

只比较“当前节点和左右孩子”

但二叉搜索树的要求其实更强：

左子树里 所有节点 都必须小于当前节点
右子树里 所有节点 都必须大于当前节点

也就是说，这不是局部条件，而是一个全局范围限制。

比如这棵树：

text

虽然：

4 < 5 不成立？这里右孩子 4 本身就已经不对

但更关键的是：

3 在 5 的右子树里
所以它也必须 > 5
可是 3 < 5

所以整棵树不是 BST。

这题至少有两种常见做法：

解法一：递归传上下界（推荐）
解法二：中序遍历判断是否严格递增

先理解：为什么“只比左右孩子”不够？

很多人第一反应会写成：

node.left.val < node.val < node.right.val

这是不够的。

因为某个节点虽然比自己的父节点合法，但可能违反了更高层祖先节点的限制。

比如：

text

看节点 6：

6 < 15，如果只和父节点比，好像没问题

但它在 10 的右子树里，所以它其实必须：

text

6 > 10

显然不满足。

所以判断 BST，一定要么：

传递合法范围
要么利用 BST 中序遍历严格递增这个性质

解法一：递归传上下界

这是最标准、最推荐掌握的做法。

思路拆解

我们递归检查每个节点时，不只看它和父节点的关系，而是给它一个合法范围：

text

(lower, upper)

表示当前节点值必须满足：

text

lower < node.val < upper

初始时根节点没有限制，可以看成：

text

(-∞, +∞)

然后：

去左子树时，上界会变成当前节点值
去右子树时，下界会变成当前节点值

这样祖先节点的限制就会一层层传下去。

一步一步写出算法

第一步：定义递归函数

const dfs = (node: TreeNode | null, lower: number, upper: number): boolean => {
    ...
}

含义是：

判断以 node 为根的子树
是否所有节点都满足 (lower, upper) 这个合法范围

第二步：处理空节点

空树天然合法：

if (node === null) {
    return true
}

第三步：判断当前节点值是否越界

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

注意一定是：

严格小于 / 严格大于

因为 BST 不允许重复值落在左边或右边。

第四步：递归检查左右子树

左子树范围：

text

(lower, node.val)

右子树范围：

text

(node.val, upper)

代码：

return dfs(node.left, lower, node.val) && dfs(node.right, node.val, upper)

第五步：从根节点开始

return dfs(root, -Infinity, Infinity)

代码实现（TypeScript）

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

function isValidBST(root: TreeNode | null): boolean {
    const dfs = (node: TreeNode | null, lower: number, upper: number): boolean => {
        if (node === null) {
            return true
        }

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

        return dfs(node.left, lower, node.val) && dfs(node.right, node.val, upper)
    }

    return dfs(root, -Infinity, Infinity)
}

复杂度分析

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

其中：

n 是节点总数
h 是树高
递归栈最坏可能到 O(n)

这一解法的优缺点

优点：

最贴合 BST 定义
边界清晰
是标准解法

缺点：

第一次写时，容易忘记范围是祖先传下来的，不只是父节点传下来的

解法二：中序遍历判断严格递增

这个做法利用了二叉搜索树的一个经典性质：

BST 的中序遍历结果一定是严格递增的

思路拆解

中序遍历顺序是：

text

左 -> 根 -> 右

如果一棵树是合法 BST，那么中序遍历得到的序列一定满足：

text

前一个值 < 后一个值

比如合法 BST：

text

    2
   / \
  1   3

中序遍历是：

text

1, 2, 3

严格递增。

所以我们只需要中序遍历整棵树，并检查：

当前访问到的值，是否严格大于上一个访问值

只要有一次不满足，就不是 BST。

一步一步写出算法

第一步：定义一个变量记录上一个访问值

let prev = -Infinity

第二步：定义中序遍历函数

const inorder = (node: TreeNode | null): boolean => {
    ...
}

第三步：先递归左子树

if (!inorder(node.left)) {
    return false
}

第四步：检查当前节点值

如果当前值不大于 prev，说明不是严格递增。

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

第五步：递归右子树

return inorder(node.right)

代码实现（TypeScript）

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

function isValidBST(root: TreeNode | null): boolean {
    let prev = -Infinity

    const inorder = (node: TreeNode | null): boolean => {
        if (node === null) {
            return true
        }

        if (!inorder(node.left)) {
            return false
        }

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

        return inorder(node.right)
    }

    return inorder(root)
}

复杂度分析

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

和第一种方法本质相同。

这一解法的优缺点

优点：

很优雅
利用了 BST 的经典性质
代码也很简洁

缺点：

需要先知道“BST 中序遍历严格递增”这个结论
prev 是一个隐式状态，第一次写时容易绕

两种解法对比

解法	时间复杂度	空间复杂度	特点
递归传上下界	`O(n)`	`O(h)`	最贴定义，最推荐
中序遍历递增判断	`O(n)`	`O(h)`	更优雅，性质很经典

如果你是第一次做这题，建议优先掌握第一种“范围限制”的思路。

手动模拟一遍

以这棵树为例：

text

用范围法看

根节点 `10`

合法范围：

text

(-∞, +∞)

10 合法。

左子树 `5`

合法范围：

text

(-∞, 10)

5 合法。

右子树 `15`

合法范围：

text

(10, +∞)

15 合法。

节点 `6`

它在 15 的左子树里，所以局部看范围是：

text

(-∞, 15)

但它同时在 10 的右子树里，所以全局还必须满足：

text

> 10

综合起来，它的合法范围应该是：

text

(10, 15)

而 6 不满足这个范围。

所以整棵树不是 BST。

面试时最容易错的点

1. 不能只比较父子节点

BST 要求的是整个子树范围合法，不只是局部合法。

2. 一定要用严格不等号

node.val <= lower || node.val >= upper

不是 < / >，而是要把等号也排除。

3. 中序遍历要求“严格递增”

不是“不下降”，而是严格递增。

因为 BST 不允许重复值。

4. `Infinity` 和 `-Infinity` 在这里很好用

它们很适合当作初始上下界。

一句话总结

这题的本质是：

每个节点都必须落在祖先节点一路传下来的合法范围里。

想写最标准解：用 递归传上下界
想用 BST 性质：用 中序遍历判断严格递增

98. 验证二叉搜索树

题目描述

示例 1

示例 2

解释

约束

核心思路

先理解：为什么“只比左右孩子”不够？

解法一：递归传上下界

思路拆解

一步一步写出算法

第一步：定义递归函数

第二步：处理空节点

第三步：判断当前节点值是否越界

第四步：递归检查左右子树

第五步：从根节点开始

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：中序遍历判断严格递增

思路拆解

一步一步写出算法

第一步：定义一个变量记录上一个访问值

第二步：定义中序遍历函数

第三步：先递归左子树

第四步：检查当前节点值

第五步：递归右子树

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍

用范围法看

根节点 10

左子树 5

右子树 15

节点 6

面试时最容易错的点

1. 不能只比较父子节点

2. 一定要用严格不等号

3. 中序遍历要求“严格递增”

4. Infinity 和 -Infinity 在这里很好用

一句话总结

推荐你最后记住的标准写法

根节点 `10`

左子树 `5`

右子树 `15`

节点 `6`

4. `Infinity` 和 `-Infinity` 在这里很好用