LeetCode 98. 验证二叉搜索树
题目描述
题意分析
判断一棵二叉树是否为有效的二叉搜索树，返回布尔值。对于每个节点，它左子树中的所有值都必须严格小于该节点，右子树中的所有值都必须严格大于该节点；这个要求要在整棵树的每个位置同时成立。
限制针对整棵子树，不能只检查节点和直接孩子。深层节点既受父节点约束，也受沿途所有祖先约束。因为大小关系是严格的，树中不能出现重复值。节点值可以等于 32 位整数的最小值或最大值，验证边界时不能把这些合法值排除。
解法：递归传递上下界
核心思路
[!blue]
沿着根到当前节点的路径，每次进入右子树都会产生一个“必须大于祖先”的下界，每次进入左子树都会产生一个“必须小于祖先”的上界。把这些条件合并后，当前节点的合法范围就是一个开区间
(lower, upper)。递归先检查当前值是否落在区间内。若它小于等于下界，或大于等于上界，已经违反祖先约束，可以立即返回
false；若通过，则继续检查两棵子树。向左递归时，所有左子树节点还必须小于当前值，所以把上界收紧为
node.val，原下界继续保留。向右递归时则把下界收紧为当前值，原上界继续保留。当前值已通过父区间检查，因此新边界一定比对应的旧边界更严格，不会丢掉更紧的祖先限制。空子树不含任何节点，不会违反限制，返回
true。从根开始不断传递并收紧区间，就把所有祖先的条件带到了每个节点；只有当前节点和左右子树全部合法，整棵子树才合法。根没有祖先，初始范围应覆盖所有合法节点值。Java 使用比
int更宽的long极值作为边界；Go 用nil表示这一侧没有边界，有边界时传递对应节点值的地址。验证过程中只读取节点值，不修改它们。
解题步骤
- 从根节点调用验证函数，初始不限制节点的合法
int取值。- 当前节点为空时返回
true。- 若当前值不在开区间内，立即返回
false。- 用
(lower, node.val)验证左子树，用(node.val, upper)验证右子树。- 只有两次验证都通过才返回
true，遇到任一违规即可短路结束。
代码实现
class Solution {
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long lower, long upper) {
if (node == null) {
return true;
}
if (node.val <= lower || node.val >= upper) {
return false;
}
// 左右子树分别继承并收紧当前节点的取值范围。
return validate(node.left, lower, node.val) && validate(node.right, node.val, upper);
}
}
func isValidBST(root *TreeNode) bool {
return validateBST(root, nil, nil)
}
func validateBST(node *TreeNode, lower *int, upper *int) bool {
if node == nil {
return true
}
if lower != nil && node.Val <= *lower {
return false
}
if upper != nil && node.Val >= *upper {
return false
}
// 递归向下传递当前子树允许的开区间边界。
return validateBST(node.Left, lower, &node.Val) && validateBST(node.Right, &node.Val, upper)
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点最多检查一次，发现违规后可以提前结束。
- 空间复杂度：$O(h)$，
h为树高，来自递归栈。平衡树为 $O(\log n)$，链状树最坏为 $O(n)$。
关键点总结
[!green]
- 合法区间汇总的是所有祖先限制，当前值通过后才能继续向下收紧。
- 左递归只更新上界，右递归只更新下界，另一侧限制继续继承。
- 使用开区间排除重复值，并让初始边界覆盖节点的全部合法取值。
解法二：中序遍历检查严格递增
核心思路
[!blue]
二叉搜索树的中序遍历按“左子树、当前节点、右子树”访问。左子树所有值更小，右子树所有值更大，两棵子树内部也满足相同规则，因此完整的中序序列一定严格递增。
反过来，若整棵树的中序序列严格递增，那么任意节点左子树的值都出现在它之前、且都更小，右子树的值都出现在它之后、且都更大；这正好满足每个节点的搜索树条件。因此，验证 BST 等价于验证中序序列严格递增。
不需要保存完整序列，只记录上一次真正访问的节点
previous。每次访问新节点时，若它的值小于等于前一个值，就直接返回false；否则更新previous。所有相邻访问都严格递增，就保证整个序列严格递增。用显式栈模拟中序：先沿左孩子不断入栈，直到没有左子树，再弹出节点进行比较；随后转到它的右子树，重复同样过程。
previous初始为空，表示还没有访问过节点，不能用某个合法整数值代替这个状态。
解题步骤
- 初始化空栈，令当前节点为根，
previous为空。- 当前节点非空时不断入栈并转向左孩子，找到下一次中序访问的位置。
- 弹出节点；若已有
previous且当前值不大于它，返回false。- 将
previous更新为当前节点，再转向其右孩子。- 当前节点为空且栈也为空时，所有节点均已通过比较，返回
true。
代码实现
class Solution {
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
TreeNode previous = null;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
if (previous != null && node.val <= previous.val) {
return false;
}
previous = node;
node = node.right;
}
return true;
}
}
func isValidBST(root *TreeNode) bool {
stack := make([]*TreeNode, 0)
node := root
var previous *TreeNode
for node != nil || len(stack) > 0 {
for node != nil {
stack = append(stack, node)
node = node.Left
}
node = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if previous != nil && node.Val <= previous.Val {
return false
}
previous = node
node = node.Right
}
return true
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点至多入栈、出栈各一次，首次出现非递增关系时即可结束。
- 空间复杂度：$O(h)$，栈最多保存一条向下路径上的节点；只额外保存一个前驱节点，无需存下整个中序序列。
关键点总结
[!green]
- BST 条件与中序序列严格递增互为充要条件，重复值也会在比较中被拒绝。
- 比较发生在中序弹出节点时，
previous表示上一次访问，不是父节点。- 用空引用表示还没有前驱，整数最小值和最大值都可以正常参与验证。
易错点总结
[!yellow]
- 只比较父节点与直接孩子，会漏掉满足父子关系却违反更早祖先限制的深层节点。
- 进入某棵子树时清空另一侧边界，会丢失从祖先继承的约束。
- Java 用
Integer.MIN_VALUE、Integer.MAX_VALUE作为开区间边界，会错误排除等于极值的合法节点。- 无论用区间还是中序法，都要拒绝相等值；只检查大小方向而放过相等，不符合本题要求。
- 中序法要比较相邻两次真正访问的节点，不能把最近压栈的节点误当成前驱，也不能用一个合法整数值充当“尚无前驱”的哨兵。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 99. 恢复二叉搜索树 | 中等 | 原题BST有两个值被交换，需要定位中序逆序点，本题只检查结构和值是否满足严格有序。 |
| 700. 二叉搜索树中的搜索 | 简单 | BST查找依赖全局有序约束，本题验证该约束不能只比较父子局部值。 |
| 补充题 204. 二叉搜索树与完全二叉树的判定 | 中等 | 都检查二叉搜索树的有序约束；补充题还要按层验证完全二叉树条件。 |
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 通过中序访问利用二叉搜索树的升序性质；本题验证整个序列严格递增，该题在第 k 次访问时取值。 |
| 173. 二叉搜索树迭代器 | 中等 | 通过中序访问利用二叉搜索树的升序性质；本题验证整个序列严格递增，该题用栈保存尚未访问的后续节点。 |
| 530. 二叉搜索树的最小绝对差 | 简单 | 通过中序访问利用二叉搜索树的升序性质；本题验证整个序列严格递增，该题比较相邻中序值的差。 |