如何根据前序遍历序列构造二叉搜索树？

简化版

BST 前序序列的第一个值是根，后面先是一段小于根的左子树，再是一段大于根的右子树。更高效的做法是用全局下标和上下界递归构造，每个值只消费一次，时间 O(n)。

详细版

朴素做法是按前序顺序逐个插入 BST，平均 O(n log n)，最坏退化 O(n²)。更好的构造方式是利用 BST 的值域约束：

维护下标 i 指向下一个待使用的前序值；
递归函数接收允许范围 (low, high)；
若 preorder[i] 不在范围内，说明它不属于当前子树，返回 null；
否则用它创建节点并 i++；
左子树范围变成 (low, root.val)；
右子树范围变成 (root.val, high)。

每个值只被创建一次，时间 O(n)，递归栈空间 O(h)。如果允许重复值，需要明确重复值放左边还是右边，并调整边界。

完整版教学

一、前序序列里隐藏了哪些信息

前序遍历顺序是根、左、右，所以序列第一个元素一定是整棵树的根。对于 BST 来说，左子树所有值小于根，右子树所有值大于根。因此在根后面的序列里，会先出现一段属于左子树的值，再出现一段属于右子树的值。

例如 preorder = [8,5,1,7,10,12]。根是 8，后面小于 8 的 [5,1,7] 属于左子树，大于 8 的 [10,12] 属于右子树。这个划分递归下去，就能恢复整棵 BST。

记忆钩子：前序给「谁先当根」，BST 给「值该落在哪个区间」；两者合起来就能构造树。

二、为什么逐个插入不是最优

按序插入当然能得到一棵 BST，因为前序序列里的节点值都来自目标树。但插入一个节点需要从根一路比较到叶子，单次代价 O(h)。如果树平衡，h≈log n，总时间 O(n log n)；如果序列是 [1,2,3,4,5]，树会退化成链表，插入总时间 O(n²)。

插入 1: 比较 0 次
插入 2: 比较 1 次
插入 3: 比较 2 次
插入 4: 比较 3 次
总比较 ≈ 0+1+2+...+(n-1)=O(n²)

上下界递归避免了反复从根查位置。它让每个值在前序流中只被检查和消费一次。

三、上下界递归的核心思想

递归函数 build(low, high) 表示「现在要构造一棵所有值都落在 (low, high) 内的子树」。如果当前前序值不在这个区间，它就不属于这棵子树，不能消费，直接返回 null。若它在区间内，它就是当前子树的根。

对于根值 x：

左子树只能放 (low, x)；
右子树只能放 (x, high)。

这样递归时不需要显式扫描哪里是左右子树分界点，边界会自动判断下一个值是否能进入当前子树。

四、代码怎么写

代码里最关键的是 idx 只向前走，不回退。当前值不属于某个子树时，返回 null，但不要 idx++，因为这个值可能属于某个祖先的右子树。

int idx = 0;

TreeNode bstFromPreorder(int[] preorder) {
    return build(preorder, Long.MIN_VALUE, Long.MAX_VALUE);
}

TreeNode build(int[] pre, long low, long high) {
    if (idx == pre.length) return null;
    int val = pre[idx];
    if (val <= low || val >= high) return null;

    idx++;
    TreeNode root = new TreeNode(val);
    root.left = build(pre, low, val);
    root.right = build(pre, val, high);
    return root;
}

用 long 边界是为了避开节点值等于 Integer.MIN_VALUE 或 Integer.MAX_VALUE 时的哨兵冲突。严格 BST 用开区间；如果题目允许重复值，条件要按重复值规则改。

五、用例推演

以 [8,5,1,7,10,12] 为例：

当前区间	当前值	结果
`(-∞,+∞)`	8	创建根 8
`(-∞,8)`	5	创建 8 的左子树根 5
`(-∞,5)`	1	创建 5 的左子树根 1
`(-∞,1)`	7	不在范围，返回 null
`(1,5)`	7	不在范围，返回 null
`(5,8)`	7	创建 5 的右子树根 7

注意值 7 在构造 1 的左右子树时都没有被消费，直到回到适合它的 (5,8) 区间才创建节点。这就是全局下标配上下界的精妙之处。

六、和「前序 + 中序」构造有什么区别

普通二叉树仅凭前序无法唯一确定，因为不知道左右子树边界。但 BST 的有序约束补上了缺失的信息，所以只给前序也能构造。前序负责提供根的出现顺序，BST 负责提供每个根的合法值域。

如果题目给的是普通二叉树，要用前序 + 中序或后序 + 中序来唯一构造；如果题目明确是 BST，前序一个序列就够了。这个区别经常被面试官拿来追问。

七、常见误区与追问

误区：前序序列单独不能构造任何树。 对普通二叉树确实不够，但对 BST 足够，因为有值域约束。
追问：为什么当前值不在区间时不能消费它？ 它可能属于祖先的右子树，消费掉会破坏后续构造。
误区：逐个插入就是最优解。 它最坏 O(n²)，上下界递归可以 O(n)。
追问：重复值怎么处理？ 必须明确重复值放左还是右，并把开闭边界规则同步调整。
误区：边界用 int 最小最大一定安全。 节点值可能等于边界，使用 long 哨兵更稳。

八、加强记忆

构造 BST 的关键是把「前序根优先」和「BST 值域」拼起来。递归函数只问一个问题：当前前序值能不能落进我的区间？能，就消费它并缩小左右子树边界；不能，就把它留给别的子树。全局下标只前进不回退，每个节点创建一次，所以时间 O(n)。记住：不在区间时返回 null，但绝对不要移动下标。

简化版

详细版