别急着建树：验证“前序遍历是不是一棵 BST”，其实是在验证你的思维边界

别急着建树：验证“前序遍历是不是一棵 BST”，其实是在验证你的思维边界

说实话，这道题Verify Preorder Sequence in BST，我特别喜欢。

不是因为它多难，而是因为它非常“算法味”：
你要是思路对了，代码又短又优雅；
你要是思路歪了，建树、递归、调试，一路把自己绕晕。

很多人第一次看到这题，第一反应是：

“我把 BST 建出来，再做一次前序遍历，对比不就完了？”

从工程角度看，能跑；
从算法角度看，完全没抓住重点。

今天这篇，我就按咱平时聊天的方式，带你把这题想透、想顺、想明白。

一、先把问题说人话：这题到底在问啥？

题目给你一个整数数组，比如：

[5, 2, 1, 3, 6]

问你一句话：

它有没有可能，是某一棵二叉搜索树（BST）的前序遍历结果？

注意两个关键词：

• BST（二叉搜索树）