LeetCode 255. 验证二叉搜索树的前序遍历序列

2026-02-05 HGNULB 约 9 分钟

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

分类

题目描述

✅ 255. 验证二叉搜索树的前序遍历序列

题意分析

给一个整数序列，判断它能不能是某棵二叉搜索树的前序遍历结果。注意是「能不能」，不需要把树建出来，也不需要指出是哪棵树；只要存在一棵合法的二叉搜索树使得其前序遍历等于该序列即可。

前序遍历的形状约束是：序列首元素是根，其后先是整段左子树，再是整段右子树。二叉搜索树的取值约束是：左子树全部小于根，右子树全部大于根。两个约束叠加后，序列被自然切成「根 + 一段全小于根的前缀 + 一段全大于根的后缀」，而且这个切点是唯一的——第一个大于根的位置。

题目默认序列中数值互不相同，所以不必纠结相等时该往哪边放。

序列长度可达 10^4，且这题的经典追问是「能否 $O(1)$ 额外空间」，说明出题人期待的不是递归建树，而是一趟线性扫描配一个能原地复用的结构。

边界包括：空序列或只有一个元素时必然合法；序列严格递减对应一条全左链；序列严格递增对应一条全右链，两者都必须判为合法。

解法：单调栈维护候选

核心思路

最朴素的做法是按定义递归：取首元素为根，从左往右找到第一个大于根的位置作为分界，检查后半段是否全部大于根，再对两段递归。这是对的，但当树退化成一条链时，每层都要重新扫描剩余的整段序列，代价退化到 $O(n^2)$，瓶颈在于「验证右半段全部大于根」这件事被反复重做了。

换个角度看：与其对每个根去验证它的右子树，不如对每个元素去回答「它必须大于谁」。在前序序列中，一旦某个值 v 大于它前面某个祖先 p，就说明遍历已经从 p 的左子树跨进了 p 的右子树。这一跨是不可逆的——p 的左子树已经彻底关闭，此后所有元素都位于 p 的右子树里，因而全部必须大于 p。

于是维护两样东西：一个栈，装着从根到当前位置这条路径上「还没有被跨进右子树」的祖先；一个下界 lower，表示「已经确认进入其右子树的那些祖先中，值最大的那个」。

不变量有两条。第一条：栈中元素自栈底到栈顶严格递减，它们正是当前节点沿路径向上、尚未被右转的祖先链。第二条：lower 等于所有已经发生右转的祖先中的最大值，因此后续任何元素都必须严格大于 lower，否则它无处安放。

判定条件由此变得极简：扫描到 val 时，若 val < lower，说明它落进了某个已经关闭的左子树区间，序列非法；否则不断把栈中比 val 小的祖先弹出，最后一个被弹出的（也就是被跨过的最深祖先，值最大）成为新的 lower；最后把 val 自己压栈，成为后续元素的候选祖先。

这里有个容易忽略但关键的细节：弹栈是从栈顶往下弹，栈顶是最小的，越往下越大，所以「最后弹出的那个」正是所有被跨越祖先中的最大值，用它更新 lower 恰好给出最紧的下界。

解题步骤

初始化空栈和 lower 为负无穷。之所以取负无穷，是因为一开始没有任何祖先被右转，对首元素不应施加任何下界限制。

从左到右遍历序列的每个值 val。之所以一趟顺扫就够，是因为前序遍历的顺序恰好就是「根先于子树、左子树先于右子树」，扫描顺序与树的结构展开顺序天然对齐。

先检查 val < lower，成立就立刻返回 false。之所以要放在弹栈之前，是因为 lower 承载的是本轮之前已经确立的硬约束，当前值必须先通过这道闸门，才谈得上去更新祖先链。

当栈非空且 val 大于栈顶时反复弹栈，每次把弹出的值赋给 lower。之所以要一直弹到栈顶大于 val 为止，是因为 val 可能一口气跨越了好几层祖先的左子树——比如从一条长左链的末端直接跳到某个高层祖先的右子树，这几层的左子树同时被关闭。

循环结束后把 val 压栈。之所以每个元素都要压，是因为它有可能是后续某段序列的祖先，必须留在候选路径上等待被跨越或被埋没。

遍历完成没有触发非法条件就返回 true。之所以不需要额外收尾检查，是因为每个元素在被处理时就已经完成了全部必要的验证，栈中残留元素只代表一条还没走完右转的路径，本身不构成矛盾。

以 preorder = [5, 2, 1, 3, 6] 走一遍。初始栈空，lower = -∞。

val = 5：不小于下界；栈空不弹；压栈得 [5]。val = 2：不小于 -∞；栈顶 5 不小于 2，不弹；压栈得 [5, 2]（自底向上递减，符合不变量）。val = 1：通过；栈顶 2 不小于 1，不弹；压栈得 [5, 2, 1]。val = 3：3 >= -∞ 通过；栈顶 1 小于 3，弹出并令 lower = 1；新栈顶 2 小于 3，弹出并令 lower = 2；新栈顶 5 大于 3，停止；压栈得 [5, 3]。此刻 lower = 2 的含义是「已经进入 2 的右子树，后面所有值都必须大于 2」，完全正确。val = 6：6 >= 2 通过；栈顶 3 小于 6，弹出令 lower = 3；栈顶 5 小于 6，弹出令 lower = 5；栈空停止；压栈得 [6]。遍历结束返回 true。

再用 preorder = [5, 2, 6, 1, 3] 检验失败路径。5 压栈得 [5]；2 压栈得 [5, 2]；6 触发弹栈，弹出 2 令 lower = 2，弹出 5 令 lower = 5，压栈得 [6]；1 与 lower = 5 比较，1 < 5 成立，立即返回 false。直觉上讲，序列在 6 处已经跳进了根 5 的右子树，后面再出现小于 5 的 1 就无处安放，判定正确。

代码实现

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)$，凭据是每个元素恰好入栈一次、出栈至多一次，内层 while 循环的总执行次数被出栈总数 $n$ 卡住，因此虽然有嵌套循环但整体仍是线性的均摊代价。

空间复杂度：$O(n)$，凭据是栈最多同时装下整条从根到当前节点的路径，当输入是严格递减序列（一条全左链）时栈会装满所有 $n$ 个元素；若允许原地改写输入数组，可以用一个下标指针把栈压进 preorder 自身，把额外空间降到 $O(1)$。

关键点总结

遍历序列的合法性验证，往往不需要真的把树建出来，只要能把树的结构约束翻译成序列上的「每个位置必须满足的数值区间」，就能退化成一趟扫描。

「一旦跨进右子树，左子树就永久关闭」是二叉搜索树前序序列的核心不可逆性，把它抽象成一个只增不减的下界变量，是本题从 $O(n^2)$ 降到 $O(n)$ 的全部关键。

单调栈在这里的语义不是「找下一个更大元素」，而是「维护当前节点的祖先链」。识别出栈中元素的真实含义，比记住模板重要得多，同一套代码换个语义就能解不同的题。

弹栈时用「最后一个弹出的值」而不是「第一个弹出的值」来更新下界，因为栈自顶向下递增，最后弹出的最大，给出的约束最紧。约束类问题永远要取最紧的那个。

面试视角：这题面试官通常先接受 $O(n)$ 时间 $O(n)$ 空间的栈解法，然后追问能否做到 $O(1)$ 额外空间。标准答复是「用输入数组本身当栈，维护一个栈顶下标 top，入栈写 preorder[++top]，出栈做 top--」，能主动说出这一步会明显加分。另一个高频追问是「后序遍历序列怎么验证」，答案是从右往左扫并把比较方向整体反过来。

易错点总结

把判断写成 val < stack.peek() 就返回 false：用例 [5, 2, 1, 3, 6]，处理 2 时栈顶是 5，2 < 5 成立会误判非法，而它其实是合法的左孩子；栈顶只是当前父节点，真正的硬约束是 lower。

弹栈时只弹一次而不用 while：用例 [5, 2, 1, 3, 6]，处理 3 时只弹出 1，lower 停在 1，栈变成 [5, 2, 3] 破坏了单调递减，后续再来一个 2 时不会被拦截，错误返回 true。

用第一个被弹出的值更新 lower，例如把赋值写在 while 外面只做一次：用例 [5, 2, 1, 3, 2]，处理 3 时 lower 停在 1 而非 2，末尾的 2 大于 1 通过检查，错误返回 true，正确答案是 false。

把 if (val < lower) 放到弹栈之后：用例 [5, 2, 6, 1, 3]，处理 1 之前若先弹栈，栈顶是 6 大于 1 不会弹，lower 仍是 5，此例侥幸能过；但换成 [5, 2, 6, 4, 3]，处理 4 时先弹栈会把 lower 从 5 改成 6，随后 4 < 6 虽也返回 false，lower 的语义却已被污染，遇到 [10, 20, 15] 这类输入会得到与推导不符的中间状态，正确写法是先验后弹。

lower 初始化为 0 而不是负无穷：用例 [-5, -10, -3]，首元素 -5 就小于 0，直接返回 false，而它是合法的。

Java 里 lower 初始化为 Integer.MIN_VALUE 但序列中确实含 Integer.MIN_VALUE：用例 [-2147483648]，val < lower 为假可以通过，但若写成 val <= lower 就会误判非法，比较符必须是严格小于。

用 Stack<Integer> 且判空前就 peek()：用例 [5]，首元素时栈为空，peek() 抛 EmptyStackException，while 条件里的 !stack.isEmpty() 必须写在短路的左侧。

遍历结束后还额外要求栈必须为空：用例 [5, 2, 1]，这是一条合法的全左链，结束时栈里还留着三个元素，加这条检查会错误返回 false。

试图用「找第一个大于根的位置再递归两段」的写法但忘了验证右段全部大于根：用例 [5, 2, 6, 1]，切点在 6，右段 [6, 1] 若不校验就递归下去，1 会被当成 6 的左孩子而漏判，错误返回 true。

Go 里 lower 用 math.MinInt32 但栈元素声明成 int，同时把弹栈写成 stack = stack[:len(stack)-1] 之后才读取被弹值：用例 [5, 2, 1, 3, 6]，读到的是已经被截断的位置，lower 更新成错误的值，必须先取值再截断。

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	树已经建好，验证方式是自顶向下传递上下界或中序检查递增
1008. 前序遍历构造二叉搜索树	中等	同一份前序输入但要真的建出树，用上界剪枝控制递归返回时机
331. 验证二叉树的前序序列化	中等	序列含空节点标记，验证依据变成槽位计数而非数值大小关系
105. 从前序与中序遍历序列构造二叉树	中等	无数值大小假设，必须借助中序定位根来切分左右子树
739. 每日温度	中等	同样的单调栈骨架，但栈中元素代表待解决的下标而非祖先链