如何判断一个序列是否可能是二叉搜索树的前序遍历？

简化版

可以用单调栈和下界判断。遍历前序序列时，栈表示尚未完成右子树的祖先；当当前值大于栈顶，说明从左子树切到某个祖先的右子树，弹栈并更新下界。之后若遇到小于下界的值，就不可能是合法 BST 前序。

详细版

前序是根、左、右。BST 中一旦进入某个节点的右子树，后续值都必须大于该节点。单调栈做法：

lower = -∞，表示当前值必须大于的下界；
遍历每个值 x；
若 x < lower，违反 BST 约束，返回 false；
当栈不空且 x > stack.peek()，说明正在从若干左子树回到右子树，弹栈并把弹出的值设为新的下界；
把 x 入栈。

每个元素最多入栈出栈一次，时间 O(n)，空间 O(n)。如果允许重复值，要根据重复值放置规则调整比较符。

完整版教学

一、为什么验证前序比构造前序更像约束检查

给定一个序列，问题不是让你真的建树，而是判断它能否由某棵 BST 的前序遍历产生。前序的特点是根先出现，然后左子树，再右子树。BST 的特点是左小右大。一旦序列从某个节点的左侧区域切换到右侧区域，就不能再出现小于这个节点的值。

例如 [5,2,1,3,6] 合法：5 是根，2、1、3 在左子树，6 在右子树。[5,2,6,1] 不合法：看到 6 后已经进入 5 的右子树，后面又出现 1，小于 5，违反下界。

记忆钩子：验证 BST 前序的核心是「右拐以后不能再低于拐弯的祖先」。

二、下界 lower 是怎么来的

lower 表示当前节点必须大于的最小值。初始没有下界。当前序列从某个祖先的左子树切换到右子树时，这个祖先就成为后续所有节点的下界。因为右子树里所有值都必须大于祖先。

看 [5,2,1,3,6]：

5 入栈，lower=-∞
2 < 5，仍在 5 的左侧，入栈
1 < 2，仍在 2 的左侧，入栈
3 > 1，弹 1，lower=1
3 > 2，弹 2，lower=2，说明进入 2 的右子树
6 > 3，弹 3，lower=3
6 > 5，弹 5，lower=5，说明进入 5 的右子树

之后任何值若小于 5，就不可能合法。

三、栈里保存的是什么

栈保存的是一条还没有完全处理完的祖先路径，并且通常呈递减趋势。当前值小于栈顶时，它可以继续作为栈顶节点的左子孙；当前值大于栈顶时，说明栈顶节点的左侧已经结束，要不断弹出，直到找到当前值应该挂在哪个祖先的右侧。

当前关系	含义	操作
`x < stack.peek()`	继续走左子树	直接入栈
`x > stack.peek()`	从左侧回到右侧	弹栈并更新 lower
`x < lower`	跌破已确定下界	不合法

这个过程和递归构造中的区间类似，只是用栈把递归返回的过程压缩成迭代。

四、代码实现

代码非常短，但比较符很关键。严格 BST 下，如果不允许重复值，遇到 x < lower 不合法，入栈弹栈用 >。若题目对重复值有特别规则，需要同步修改。

boolean verifyPreorder(int[] preorder) {
    int lower = Integer.MIN_VALUE;
    Deque<Integer> stack = new ArrayDeque<>();

    for (int x : preorder) {
        if (x < lower) return false;
        while (!stack.isEmpty() && x > stack.peek()) {
            lower = stack.pop();
        }
        stack.push(x);
    }
    return true;
}

如果节点值可能等于 Integer.MIN_VALUE，可以把 lower 改成 long，初始为 Long.MIN_VALUE。这样不会因为哨兵和真实值冲突而误判。

五、为什么弹出的最后一个值可以作为下界

当 x 大于若干栈顶元素时，它不可能再属于这些节点的左子树，只能进入它们某个祖先的右侧。弹出的节点代表已经完成左子树并进入右子树的边界，其中最后弹出的最大祖先是当前必须大于的下界。之后的节点仍处在这个右侧区域内，不能再低于它。

用 [8,5,1,7,10,6] 看非法点：

10 到来时弹出 7、5、8，lower=8
后面 6 < 8，说明已经进入 8 的右子树后又出现小于 8 的值
所以不合法

这里的 6 可能大于 5，但它已经错过了 5 的右子树位置，不能再回去。

六、和递归上下界验证的关系

也可以像构造 BST 一样用递归上下界验证，每次判断当前值是否落在合法区间。但单调栈更适合只验证序列，不需要建树，也不需要切分数组。两者本质一样：都在维护「当前值的合法范围」。

方法	思路	时间	空间
构造再验证	先建 BST 再检查	O(n log n) 到 O(n²)	O(n)
递归上下界	用前序下标和区间消费	O(n)	O(h)
单调栈下界	迭代维护祖先边界	O(n)	O(n)

面试中单调栈版本很能体现对前序和 BST 结构的理解，但也更容易讲不清。讲清 lower 的来源是重点。

七、常见误区与追问

误区：只要序列先降后升就是合法。 BST 前序可以多次局部变化，关键是不能跌破已经确定的下界。
追问：为什么看到更大值要弹栈？ 这表示离开若干节点的左子树，进入它们的右侧区域。
误区：弹栈后 lower 可以随便取栈顶。 lower 应更新为弹出的节点值，因为它是已经进入右子树的祖先边界。
追问：重复值怎么办？ 要先定义重复值放左还是放右，再调整 <、<=、> 的规则。
误区：出现小于栈顶就一定非法。 小于栈顶通常只是继续左子树，只有小于 lower 才非法。

八、加强记忆

这题可以记成「栈存祖先，下界防回头」。前序序列一路向左时不断入栈；一旦出现更大的值，就弹出若干祖先，说明进入这些祖先的右子树。进入右子树后，后续值再小于这个祖先就等于走回头路，必然非法。真正要盯住的是 lower，它记录了当前序列已经越过的最低祖先边界。

简化版

详细版