LeetCode 面试题 04.05. 合法二叉搜索树
题目描述
题意分析
判断二叉树是否满足严格搜索树规则：每个节点左子树中的全部节点都比它小，右子树中的全部节点都比它大，并且左右子树也分别合法。约束会作用于更深的后代，因此只比较直接父子节点不够，重复值也不能通过。
解法：DFS 区间校验
核心思路
[!blue]
用一个开区间同时携带所有祖先的约束。dfs(node, lower, upper)检查以node为根的子树能否放在值域(lower, upper)中。进入该子树的每个节点都必须满足lower < val < upper；下界概括了必须大于的祖先，上界概括了必须小于的祖先。当前节点通过范围检查后，递归左子树时把上界改成当前值，保留下界；递归右子树时把下界改成当前值，保留上界。由于当前值已经位于原区间内部，新区间只会收窄，不会放松任何祖先限制。这样每个后代都同时接受当前位置的限制与全部继承限制。
若某个值等于边界或越过边界，就违反了严格大小关系，立即失败。空节点没有需要检查的值，返回真；当前值合法且两个子树都通过时，才返回真。左右结果用短路与连接，一侧失败便无需继续另一侧。
初始范围必须容纳所有合法节点值。节点值使用 32 位整数范围，而边界使用 64 位整数极值；这样合法的最小、最大节点值都严格位于初始范围内，也无需通过加减 1 调整边界，避免端点溢出。
解题步骤
- 以宽整数的最小、最大值作为初始边界。
- 空节点直接通过。
- 当前值小于等于下界，或大于等于上界，都返回
false。- 左子树递归范围为
(lower, val)，右子树为(val, upper)，两边同时通过才返回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)$，每个节点至多检查一次。
- 空间复杂度：$O(h)$，递归栈由树高决定。
关键点总结
[!green]
- 边界来自全部祖先，不只是父节点。
- 严格大小关系用开区间表达，重复值不能通过。
- 哨兵要位于合法节点值域之外。
易错点总结
[!yellow]
- 只比较节点与直接孩子：漏掉更深后代对祖先的违反。
- 递归时不收窄边界：祖先约束没有传下去。
- 允许等于边界：重复值被误判合法。
- 使用 int 极值作为开区间哨兵：真实端点值会被排除。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 99. 恢复二叉搜索树 | 中等 | 原题BST有两个值被交换，需要定位中序逆序点，本题只检查结构和值是否满足严格有序。 |
| 700. 二叉搜索树中的搜索 | 简单 | BST查找依赖全局有序约束，本题验证该约束不能只比较父子局部值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！