题目

思路

一句话：BST 的“合法”不是父子之间的局部比较，而是每个节点都要满足所有祖先留下的全局约束。

先想最直白的做法：对每个节点只检查 左孩子 < 自己 < 右孩子。它为什么不够？因为它只看一层父子关系，管不住更上面的祖先。前面 [10,5,15,null,null,6,20] 的例子就说明了这一点：6 比父亲 15 小，却违反了“必须大于祖先 10”的约束。

更严格但笨的做法是：对每个节点都去扫一遍它的左子树，确认所有值都小于它；再扫一遍右子树，确认所有值都大于它。这样每个节点可能被多个祖先重复检查，总代价会到 O(n²)，明显不划算。

关键观察：BST 的合法性有两条等价刻画：

• 中序遍历严格递增。 按「左 → 根 → 右」访问 BST，得到的值序列必然从小到大排列；反过来，如果中序序列严格递增，那么这棵树也一定是 BST。
• 每个节点都有一个允许值区间。 从根开始，根的可取范围是 (-∞, +∞)；往左走时，父节点的值成为新的上界；往右走时，父节点的值成为新的下界。

两条路都能一次遍历完成。本文主推区间递归：它最贴合题目“左子树全部小于、右子树全部大于”的字面定义，也最好记。

解法

定义辅助函数 valid(node, low, high)，表示判断以 node 为根的子树是否完全落在开区间 (low, high) 内：

1. 若 node 为空，返回 true，空树视为合法。
2. 若 node.val 不满足 low < node.val < high，返回 false。
3. 递归检查左子树，上界收紧为当前值：valid(node.left, low, node.val)。
4. 递归检查右子树，下界收紧为当前值：valid(node.right, node.val, high)。
5. 左右都合法，整棵子树才合法；根节点入口调用 valid(root, -∞, +∞)。

以合法树 [4,2,6,1,3,5,7] 为例，区间从根向下逐渐收紧：