LeetCode 面试题 04.05. 合法二叉搜索树

2022-12-23 HGNULB 约 9 分钟

文章信息 7 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 1-2 小米程序员面试金典（第 6 版）

题目描述

✅ 面试题 04.05. 合法二叉搜索树

题意分析

给定一棵二叉树的根节点，判断它是否是一棵合法的二叉搜索树。合法的定义是：任意节点的左子树中所有节点的值都小于它，右子树中所有节点的值都大于它，并且左右子树本身也都是二叉搜索树。注意定义里说的是"子树中所有节点"，不是"左右孩子"，这个区别就是本题全部的陷阱所在。

约束里最关键的信号是节点值可以取到 int 的边界（题目允许 -2^31 到 2^31 - 1）。这直接决定了"用 Integer.MIN_VALUE / Integer.MAX_VALUE 当初始上下界"是不安全的——一旦树里真的存在这个值，边界判断就会把合法的节点误判成非法。所以要么把边界类型提升到 long，要么改用"允许为空"的边界表示。

边界上要覆盖：空树（按定义是合法的 BST，返回 true）；单节点；值相等的节点（BST 要求严格大小关系，出现相等即非法）；以及最经典的反例——某个节点满足与其父节点的局部关系，却违反了更上层祖先施加的约束。

解法：DFS 区间校验

核心思路

最容易写出也最容易错的暴力是"逐节点检查 node.left.val < node.val < node.right.val"。它的瓶颈不是效率而是正确性：这个检查只覆盖了父子这一层的局部关系，完全没有把祖先的约束传下去。经典反例是根为 5、左孩子 1、右孩子 4，而 4 的左右孩子是 3 和 6——每一对父子看起来都合法，但 3 落在根 5 的右子树里却小于 5，整棵树并不是 BST。

由此得到关键观察：BST 的约束不是父子之间的局部不等式，而是每个节点身上都背着一个由所有祖先累积而成的取值区间。一个节点是某个祖先的左子树成员，就意味着它必须小于那个祖先；是右子树成员，就必须大于那个祖先。把所有祖先的约束求交，恰好是一个开区间 $(lower, upper)$。

于是把状态定义成：dfs(node, lower, upper) 返回"以 node 为根的子树，在其所有节点的值都必须落在开区间 $(lower, upper)$ 内的前提下，是否是合法 BST"。递推关系是：先检查 node.val 是否落在区间内；然后左子树继承 $(lower, node.val)$——因为左子树的所有节点既要满足原有的下界，又要小于当前节点；右子树继承 $(node.val, upper)$。终止条件是 node == null 时返回 true（空子树平凡合法）。初始调用用 $(-\infty, +\infty)$，表示根节点不受任何祖先约束。

这个定义之所以正确，是因为它把"子树中所有节点都要小于/大于某祖先"这条全局条件，转化成了沿路径逐层收窄的区间，且每个节点只需与自己的区间比较一次——约束的传递性替代了对整棵子树的枚举。至于 $\pm\infty$ 的表示，代码里用 long 的 Long.MIN_VALUE / Long.MAX_VALUE（Go 里是 -1<<63 和 1<<63-1），因为节点值只有 int 范围，它们必然严格落在这两个 long 边界之内，不会误伤。

解题步骤

入口调用 dfs(root, Long.MIN_VALUE, Long.MAX_VALUE)。用 long 而不是 int 的边界，是为了给 Integer.MIN_VALUE、Integer.MAX_VALUE 这两个合法取值留出比较空间。若用 int 边界，根节点值恰为 Integer.MIN_VALUE 时，val <= lower 会成立，合法树被误判。

递归第一步：node == null 返回 true。空子树没有任何节点需要校验，天然满足区间约束；同时这也是递归的出口，保证有限层后终止。

第二步：检查 node.val <= lower || node.val >= upper 则返回 false。用的是闭合的失败条件（即区间是开区间），因为 BST 要求严格大小关系，值相等就非法。这一行同时完成了"与所有祖先比较"的工作——不需要回头访问任何祖先节点，约束已经通过参数传下来了。

第三步：递归左子树 dfs(node.left, lower, node.val)。上界收窄为当前节点值：左子树里的每个节点都必须小于当前节点。下界保持不变，因为祖先施加的下界依然有效。

第四步：递归右子树 dfs(node.right, node.val, upper)。下界收窄为当前节点值，上界保持不变，理由对称。

用 && 连接左右两个递归结果并返回。短路求值让左子树一旦发现非法就立刻停止，不再遍历右子树，是个免费的剪枝。

以经典反例 root = [5, 1, 4, null, null, 3, 6] 走一遍（根 5，左孩子 1，右孩子 4；4 的左孩子 3、右孩子 6）：

dfs(5, -∞, +∞)：5 落在区间内，通过。递归左子树 dfs(1, -∞, 5) 和右子树 dfs(4, 5, +∞)。

dfs(1, -∞, 5)：1 在 $(-\infty, 5)$ 内，通过；左右孩子都是空，返回 true。

dfs(4, 5, +∞)：检查 4 >= upper? 不成立；检查 4 <= lower，即 4 <= 5 成立，立刻返回 false。整棵树被判为非法，正确。注意如果只做父子局部比较，会看到 4 是 5 的右孩子且 4 < 5——但那个比较本身就是错的方向，局部法在这里已经翻车；即便改成检查 4 > 5 失败，也无法解释更深层的 3 为什么非法。

再走一个"局部全对但整体错"的例子 root = [10, 5, 15, null, null, 6, 20]：dfs(10, -∞, +∞) 通过；dfs(5, -∞, 10) 通过，是叶子；dfs(15, 10, +∞) 通过；接着 dfs(6, 10, 15)——6 <= 10 成立，返回 false。这里 6 和它的父节点 15 的关系是完全合法的（6 < 15，作为左孩子没问题），只有把根 10 传下来的下界纳入才能发现问题，这正是区间法相对局部法的价值所在。

最后走一个合法例子 root = [2, 1, 3]：dfs(2, -∞, +∞) 通过；dfs(1, -∞, 2) 通过，左右为空；dfs(3, 2, +∞) 通过，左右为空。全部返回 true，整体判定合法。

代码实现

class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean dfs(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return dfs(node.left, lower, node.val) && dfs(node.right, node.val, upper);
    }
}

func isValidBST(root *TreeNode) bool {
    return dfs(root, -1<<63, 1<<63-1)
}

func dfs(node *TreeNode, lower int64, upper int64) bool {
    if node == nil {
        return true
    }
    v := int64(node.Val)
    if v <= lower || v >= upper {
        return false
    }
    return dfs(node.Left, lower, v) && dfs(node.Right, v, upper)
}

复杂度分析

时间复杂度：$O(n)$，n 为节点数。每个节点恰好被 dfs 访问一次，节点内部只做常数次比较；短路求值只会让访问变少，不会变多。

空间复杂度：$O(h)$，h 为树高，来自递归调用栈。平衡树是 $O(\log n)$，退化成链时是 $O(n)$——这正是本题在极端数据下可能爆栈的原因，若面试官追问可改成显式栈的中序遍历。

关键点总结

"子树中所有节点"这类措辞，意味着约束是沿路径累积的，不能只看父子。凡是题目条件里出现"整个子树""所有后代"，第一反应就该是把祖先信息作为参数向下传，而不是在每个节点局部检查。

把全局约束转成沿递归下传的参数，是树形 DFS 的核心技巧。上下界、路径和、路径上的最大值、已访问集合，都是同一类"下传状态"；它们的共同特点是父节点能 $O(1)$ 算出子节点该继承什么。

边界哨兵必须严格超出数据的取值域。节点值能取满 int，哨兵就得用 long；这条规则可以推广：任何用极值当"无约束"标记的写法，都要先确认这个极值不可能是合法数据。更稳妥的替代是用可空类型（Java 的 Integer、Go 的 *int）表示"无边界"。

BST 要求严格不等，相等即非法。判断写成 <= / >= 而不是 < / >，这一个等号决定了重复值用例的对错。

面试视角：准备好"区间法"和"中序遍历法"两套，并说清各自的取舍。中序法利用"BST 的中序遍历严格递增"，只需维护一个 prev 指针逐个比较，代码更短、不需要处理哨兵溢出，而且改成迭代版后能做到 $O(h)$ 空间且可提前退出；区间法的优势是逻辑更直白、易于扩展（比如同时统计合法 BST 子树）。面试里先写区间法，再主动补一句"也可以用中序遍历判断是否严格递增，用 long 型 prev 或用 null 表示未初始化来规避边界问题"，比只会一种更稳。

易错点总结

错误写法：只比较父子，写成 node.val > node.left.val && node.val < node.right.val 后递归 → 用例 root = [10, 5, 15, null, null, 6, 20]：每一对父子都满足局部关系，返回 true，正确答案是 false（6 在根 10 的右子树里却小于 10）。

错误写法：上下界用 int 并初始化为 Integer.MIN_VALUE / Integer.MAX_VALUE → 用例 root = [-2147483648]：根节点值恰好等于下界，node.val <= lower 成立返回 false，正确答案是 true。

错误写法：判断写成 node.val < lower || node.val > upper（漏了等号） → 用例 root = [1, 1]（根和左孩子都是 1）：1 < 1 不成立，检查通过，返回 true，正确答案是 false——BST 不允许重复值。

错误写法：递归左子树时传 dfs(node.left, lower, upper)（忘记收窄上界） → 用例 root = [3, 5]（根 3，左孩子 5）：左子树的上界仍是 $+\infty$，5 通过检查，返回 true，正确答案是 false。

错误写法：左右子树的边界传反，写成 dfs(node.left, node.val, upper) → 用例 root = [2, 1, 3]：左孩子 1 被要求大于 2，返回 false，正确答案是 true——完全合法的树被判非法。

错误写法：空节点返回 false → 用例 root = [1]：叶子节点的左右孩子都是空，两个 false 让整棵树被判非法，正确答案是 true。空子树是平凡合法的，递归出口必须返回 true。

错误写法：改用中序遍历法时，prev 初始化为 Integer.MIN_VALUE 并写 if (val <= prev) return false → 用例 root = [-2147483648]：第一个节点就与初始 prev 相等被判非法。中序法的 prev 必须用 long 或用"是否已初始化"的布尔标志。

错误写法：中序遍历法里写 if (val < prev)（漏等号） → 用例 root = [1, 1]：中序序列是 [1, 1]，非严格递增却被放行，返回 true。BST 的中序必须严格递增。

错误写法：Go 里 dfs(root, math.MinInt32, math.MaxInt32) 且参数声明为 int → 用例 root = [2147483647]：v >= upper 成立返回 false。Go 的 int 虽然是 64 位，但哨兵取成 int32 的极值就退化成了上面那个 Java 的错误。

错误写法：Go 里忘记 int64(node.Val) 直接拿 node.Val 和 int64 参数比较 → 编译报错，int 与 int64 是不同类型不能直接比较，必须显式转换。

错误写法：为了"提前退出"把 && 改成先把两个递归结果各存一个变量再相与 → 用例是一棵左子树极早就非法、右子树极深的树：失去短路后右子树被完整遍历，虽然答案仍对，但在退化成链的深树上白白多走一遍，且更容易触及栈深度上限。

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	完全同题的主站版本，常被追问中序迭代写法与提前退出
230. 二叉搜索树中第 K 小的元素	中等	同样利用中序有序，但要在遍历中计数并提前终止而非全程校验
面试题 17.12. BiNode	简单	中序遍历的同时改指针把树拉平成链表，重点在遍历时修改结构
426. 将二叉搜索树转化为排序的双向链表	中等	中序串联并额外接回首尾形成环，前驱后继都要维护
538. 把二叉搜索树转换为累加树	中等	走反序中序（右-根-左）并累加后缀和，方向与本题相反
面试题 04.06. 后继者	中等	同样靠上下界思想定位，但只沿一条路径下行而不遍历整棵树
333. 最大二叉搜索子树	中等	需要自底向上返回子树的合法性与极值，是区间法的后序对偶写法