98. 验证二叉搜索树

题目描述

验证是否为二叉搜索树：左子树所有值 < 根 < 右子树所有值(对每个节点都成立)。

思路解析

根的范围是 (−∞, +∞)。走到左孩子，上界收紧为"父值"；走到右孩子，下界收紧为"父值"。每个节点的值必须严格落在自己的 (low, high) 内，否则不是 BST。

根 5 · 范围 (−∞, +∞)：根 5 没有任何约束，范围 (−∞, +∞)，通过。往左走上界变 5、往右走下界变 5。

3 ∈ (−∞,5) · 8 ∈ (5,+∞)：左孩子 3 要在 (−∞, 5)：✓。右孩子 8 要在 (5, +∞)：✓。范围继续往下收紧。

关键 · 4 必须 ∈ (3, 5)：4 是 3 的右孩子，但它在 5 的左子树里，所以范围是 (3, 5)——上界 5 是从祖父 5 传下来的！4 落在区间内 ✓。如果 4 写成了 6，只跟父亲 3 比会以为合法，但 6 ≥ 5 其实违规。

右子树 · 7,9 也合法：7 在 (5, 8)、9 在 (8, +∞)，都通过。所有节点都落在各自范围内 → 是合法 BST。

另一招更简洁：BST 的中序遍历必然严格递增，中序走一遍看是否一直变大即可(复用 94)。两种方法都很经典。

参考代码（Python）

1def valid(node, low, high):
2    if not node: return True
3    if not (low < node.val < high):       # 越界即非法
4        return False
5    return (valid(node.left, low, node.val) and    # 左: 上界收紧
6            valid(node.right, node.val, high))    # 右: 下界收紧
7return valid(root, float(class="cl-str">"-inf"), float(class="cl-str">"inf"))

复杂度分析

• 时间复杂度：O(n) —— 每个节点检查一次
• 空间复杂度：O(h) —— 递归栈

套路模板

记住骨架：空则真、越界则假、左子树收上界、右子树收下界。「往下传递累积约束」是树递归的一个重要范式。

1def dfs(node, low, high):
2    if not node: return True
3    if not (low < node.val < high): return False
4    return dfs(node.left, low, node.val) and \
5           dfs(node.right, node.val, high)

易错点

• ❌ 只比较 node 和直接父亲 → ✅ 传 (low,high) 累积约束（右子树里的节点也要 > 祖先根，光跟父比会漏判）
• ❌ 用 <= 允许相等 → ✅ BST 要严格 low < val < high（相等值不符合严格 BST 定义）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。