98. 验证二叉搜索树

🔍 题目目标

判断一棵二叉树是否为有效的二叉搜索树（BST），定义如下：

左子树所有节点 < 根节点
右子树所有节点 > 根节点
且左右子树也必须是二叉搜索树

一、算法逻辑（逐步通顺讲解每一步思路）

该算法使用了递归 + 上下界限制法，即为每个节点维护一个值域区间 [left, right]，确保节点值在区间内才是有效的 BST。

✅ 1️⃣ 初始调用：
从根节点 root 开始判断，默认左右边界为负无穷和正无穷，即 (-inf, +inf)。表示当前节点理论上可以是任意值。

✅ 2️⃣ 递归边界判断：
如果当前节点为 None，说明是空树或到达叶子节点，属于有效 BST，返回 True。

✅ 3️⃣ 当前节点合法性判断：
获取当前节点值 x = root.val，判断其是否满足。

即节点值必须严格在当前区间范围内。

✅ 4️⃣ 递归判断左右子树：

左子树的合法区间更新为 (left, x)，即值必须 < 当前节点值；
右子树的合法区间更新为 (x, right)，即值必须 > 当前节点值；
两者都必须返回 True，整个树才合法。

✅ 5️⃣ 使用逻辑与 and 串联判断：
只有当前节点合法且左右子树也为 BST，整体才能返回 True。

二、核心点总结

该算法的核心是：

递归地对每个节点维护上下边界区间 [left, right]，判断其值是否符合 BST 的定义，并递归验证左右子树。

✅ 采用“值域约束”方式，严格验证 BST 的定义
✅ 上下界会随着递归深入而收紧，更精确限制节点取值
✅ 非常适合处理“全局性条件”的验证场景，如 BST 中的跨层约束
✅ 简洁高效，是判断 BST 有效性的经典做法

class Solution:def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:if root is None:return True# x = root.valreturn left < root.val < right and \self.isValidBST(root.left, left, root.val) and \self.isValidBST(root.right, root.val, right)

三、时间复杂度分析

每个节点仅访问一次；
每次访问包含常数操作和两次递归调用。

因此，时间复杂度为：

O(n)，其中 n 是二叉树中的节点数

四、空间复杂度分析

空间主要来自递归栈深度：

最坏情况是退化成链表时递归深度为 n
最好情况（平衡树）递归深度为 log n

因此空间复杂度为：

O(h)，其中 h 是树的高度，最坏情况下为 O(n)，平均为 O(log n)

✅ 总结一句话

本算法通过上下界约束方式递归判断每个节点是否符合 BST 条件，时间复杂度 O(n)，空间复杂度 O(h)，是判断有效二叉搜索树的最经典、最推荐方案之一。

非常好，这里我们就结合输入用例：

root = [5,1,4,null,null,3,6]

用例讲解

root = [5,1,4,null,null,3,6]

来详细还原这段递归算法每一步的过程，帮你彻底理解 isValidBST(root, left, right) 的行为。包括每一步的参数、判断条件、递归路径，以及在什么情况下返回 True 或 False。

🔧 准备工作：还原树结构

先把这个数组构造的二叉树结构还原出来（按 LeetCode 层序规则）：

        5/ \1   4/ \3   6

我们希望判断这个树是否是合法的 BST。

🧠 递归过程逐步模拟（输入：[5,1,4,null,null,3,6]）

我们从根节点 5 开始调用：

✅ Step 1：`isValidBST(5, -inf, +inf)`

当前节点值：5
是否满足范围：-inf < 5 < +inf ✅
继续检查左右子树：

→ Step 1.1：`isValidBST(1, -inf, 5)`（左子树）

当前值：1
范围：-inf < 1 < 5 ✅
继续递归左右：

→ Step 1.1.1：`isValidBST(None, -inf, 1)` → 空树 ✅

→ Step 1.1.2：`isValidBST(None, 1, 5)` → 空树 ✅

↩️ 1 的子树都合法 → 返回 True

→ Step 1.2：`isValidBST(4, 5, +inf)`（右子树）

当前值：4
范围：5 < 4 < +inf ❌ 不合法！

↩️ 4 不在合法范围内，直接返回 False！

此处是整个递归“剪枝”发生的位置

⛔ 说明什么？说明你不能只看当前节点的左右是否比自己小或大，还要满足“整个路径”上的上下界限制（即必须大于所有祖先节点中要求大的那一边）。

❌ 最终结果：返回 False

因为右子树 4 违反了 BST 的约束条件（其值 < 根节点 5，却出现在右子树），因此整个树不是有效的 BST。

📌 小结：每次递归都做了什么？

步骤	当前节点	left bound	right bound	判断是否合法	结果
1	5	-∞	+∞	-∞ < 5 < ∞ ✅	继续
1.1	1	-∞	5	-∞ < 1 < 5 ✅	继续
1.1.1	None	-∞	1	空节点 ✅	True
1.1.2	None	1	5	空节点 ✅	True
1.2	4	5	+∞	❌ 4 < 5	False