验证二叉搜索树

最容易踩的笨/错办法：对每个节点只比它和左右直接孩子。问题是 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 的中序遍历必然严格递增，中序走一遍看是否一直变大即可——两种方法都很经典。

迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

边界三连：验证二叉搜索树 的边界先看最小规模、空输入和会触发特殊分支的极端样例。

面试追问：验证二叉搜索树 的追问重点，是把动画里的状态定义、边界和复杂度讲成自己的话。