题目描述
验证是否为二叉搜索树：对每个节点，左子树所有值 < 它 < 右子树所有值。
思路解析
最容易踩的笨/错办法：对每个节点只比它和左右直接孩子。问题是 BST 要求是「子树里所有节点」都满足，一个深处的孩子可能比某个祖先还大，光看父子三人组根本发现不了，会把非法树判成合法。
转折：把约束当参数一路往下传。根的范围是 (−∞, +∞)；走到左孩子时上界收紧为「父值」、走到右孩子时下界收紧为「父值」。每个节点的值必须严格落在自己继承来的 (low, high) 内。这样祖先的约束就被「带」到了每个后代身上，不会再漏判深处的节点。
根 5 · 范围 (−∞, +∞)：根 5 不受任何约束，范围 (−∞, +∞)，通过。往左走时把上界改成 5、往右走时把下界改成 5，分别传给两个孩子。
左孩子 3 ∈ (−∞, 5)：左孩子 3 继承的范围是 (−∞, 5)：上界由父亲 5 收紧。3 < 5 ✓。再往下：3 的左孩子拿 (−∞, 3)、右孩子拿 (3, 5)。
右孩子 8 ∈ (5, +∞)：右孩子 8 继承范围 (5, +∞)：下界由父亲 5 收紧。8 > 5 ✓。8 的左孩子将拿 (5, 8)、右孩子拿 (8, +∞)。
1 ∈ (−∞, 3) · 都通过：3 的左孩子 1：范围 (−∞, 3)，1 < 3 ✓。叶子，无需再往下。
关键 · 4 必须 ∈ (3, 5)：全题最关键的一个节点：4 是 3 的右孩子，但它整体在 5 的左子树里，所以范围是 (3, 5)——下界 3 来自父亲、上界 5 来自祖父。3 < 4 < 5 ✓。这正是「只比父亲」会漏掉的约束。
反例对照 · 把 4 改成 6：把这个位置换成 6 看看：只跟父亲 3 比，6 > 3 像是合法；可它落在 5 的左子树，必须 < 5。6 ≥ 5，越界！错办法会放过它，带上下界的办法一眼抓住。
越界即非法 · return False：一旦某节点落在自己的 (low, high) 之外，立刻判定整棵树不是 BST，return False。回到正例：正因为原来的 4 严格落在 (3,5) 内，才得以继续；下面把右子树也验完。
右子树 7,9 也合法 · True：回到正例的 8 这一支：左孩子 7 在 (5, 8) ✓、右孩子 9 在 (8, +∞) ✓。所有节点都落在各自范围内 → 是合法 BST, return True。
「祖先施加的约束，沿递归一路带给后代」是树递归的一个重要范式。另一招更简洁：BST 的中序遍历必然严格递增，中序走一遍看是否一直变大即可——两种方法都很经典。
参考代码（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 # 左: 上界收紧为 node.val
6 valid(node.right, node.val, high)) # 右: 下界收紧为 node.val
7return valid(root, float(class="cl-str">"-inf"), float(class="cl-str">"inf"))复杂度分析
- 时间复杂度：O(n) —— 每个节点检查一次
- 空间复杂度：O(h) —— 递归栈深度等于树高 h
套路模板
记住骨架：空则真、越界则假、左子树收上界、右子树收下界。「往下传递累积约束」可迁到「修剪 BST」「区间内节点和」等题。
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) # 收上界
5 and dfs(node.right, node.val, high)) # 收下界易错点
- 错误写法：只比 node 和直接父亲/孩子 → 正确写法：传 (low, high) 累积约束往下（右子树深处的节点也必须大于某个祖先根，光跟父比会把非法树误判为合法(本题的 6 就是反例)）
- 错误写法：用 <= 允许相等 → 正确写法：BST 要严格 low < val < high（严格 BST 不允许重复值，写成 ≤ 会把有相等值的树错判为合法）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。