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 |
✅ 总结一句话
这套递归结构的关键是：每个节点必须严格落在“它所能合法存在的值域区间”内，这个区间来自于祖先节点不断递归传下来的上下界。
一旦有节点违反这个区间，即可剪枝终止。
)
(5))
