LeetCode 255. 验证二叉搜索树的前序遍历序列
题目描述
题意分析
判断一组互不相同的数，能否按“根、左子树、右子树”的顺序遍历某棵二叉搜索树得到。二叉搜索树要求左子树所有值小于根、右子树所有值大于根，只需判断是否存在这样的树，不必实际构造。
解法：单调栈维护候选
核心思路
[!blue]
前序遍历一旦开始某个节点的右子树，就不能再回到它的左子树，后续属于这部分的值必须大于该节点。用
lower保存已经进入右子树的祖先中最大的值，作为后续节点不能越过的下界。另用一个从栈底到栈顶递减的栈保存尚未跨入右侧的祖先。当前值小于栈顶时，可以继续向左下降；当前值大于栈顶时，就需要结束这条较小节点的路径，持续弹栈，直到栈空或栈顶大于当前值。最后弹出的节点是这次转入右子树的根，将它赋给
lower。连续弹出的值越来越大，最后一个给出最紧的下界；剩余栈顶若存在，则是当前节点必须小于的最近上界。先检查
val < lower，再按上述规则弹栈、入栈，就能同时满足已经确定的下界和剩余祖先的上界。题目保证数值互异，不会再次遇到等于某个已访问祖先的值。若下界被违反，说明序列试图回到已经结束的左侧区域，不可能是前序遍历。若全部数都通过，则每个数都能接入当前允许的子树范围，形成合法遍历。扫描结束不必清空栈：剩余节点只是没有右子树，并不表示输入缺失。
解题步骤
- 初始化空栈，并用最小哨兵值初始化
lower。- 从左到右读取
val，若小于lower，立即返回false。- 持续弹出所有小于
val的栈顶，每次将弹出值赋给lower。- 将
val入栈；全部数处理完成后返回true。
代码实现
class Solution {
public boolean verifyPreorder(int[] preorder) {
Deque<Integer> stack = new ArrayDeque<>();
int lower = Integer.MIN_VALUE;
for (int val : preorder) {
if (val < lower) {
return false;
}
while (!stack.isEmpty() && val > stack.peek()) {
// 持续更新到最后弹出的最大祖先值，形成最紧下界
lower = stack.pop();
}
stack.push(val);
}
return true;
}
}
func verifyPreorder(preorder []int) bool {
stack := make([]int, 0)
lower := -1 << 60
for _, val := range preorder {
if val < lower {
return false
}
for len(stack) > 0 && val > stack[len(stack)-1] {
// 持续更新到最后弹出的最大祖先值，形成最紧下界
lower = stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
stack = append(stack, val)
}
return true
}
复杂度分析
- 时间复杂度：$O(n)$，
n为序列长度，每项至多入栈、出栈一次，内层循环的总次数仍为线性。- 空间复杂度：$O(n)$，严格递减时栈可保存全部值。
关键点总结
[!green]
- 最后弹出的值最大，给出最紧右子树下界。
- 栈不等于所有祖先完整列表，已跨入右侧的约束由下界保留。
进阶：原数组模拟栈
核心思路
[!blue]
如果允许修改输入，可以把已经读取过的数组前缀当作栈，只额外维护栈大小
size和下界lower。栈顶是preorder[size - 1]，弹栈只需减小size，入栈则写入preorder[size]后增加大小。处理第
i个元素时，先将它读入局部变量val。此前栈中最多有i个元素，因此入栈位置不会超过i，只会覆盖已经读取的位置，不会破坏后续输入。判断规则与普通栈完全相同，代价是原数组内容会改变。
代码实现
class Solution {
public boolean verifyPreorder(int[] preorder) {
int size = 0;
int lower = Integer.MIN_VALUE;
for (int val : preorder) {
if (val < lower) {
return false;
}
while (size > 0 && val > preorder[size - 1]) {
lower = preorder[--size];
}
preorder[size++] = val;
}
return true;
}
}
func verifyPreorder(preorder []int) bool {
size := 0
lower := -1 << 60
for _, val := range preorder {
if val < lower {
return false
}
for size > 0 && val > preorder[size-1] {
size--
lower = preorder[size]
}
preorder[size] = val
size++
}
return true
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素仍至多入栈、出栈一次。
- 空间复杂度：$O(1)$，栈复用输入数组，不分配额外数组。
易错点总结
[!yellow]
- 只弹一次，可能漏掉连续结束的多个祖先，无法把下界提高到正确位置。
- 用当前栈顶作拒绝下界，会误拒合法左孩子。
- 要求结束栈空，会误拒合法全左链。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 98. 验证二叉搜索树 | 中等 | 原题直接验证树结构的上下界，本题要从前序序列模拟进入右子树后形成的下界。 |
| 剑指 Offer 33. 二叉搜索树的后序遍历序列 | 中等 | 同样验证遍历序列能否来自BST，但后序与前序的根位置和扫描方向不同。 |