LeetCode 1008. 前序遍历构造二叉搜索树

2024-08-29 HGNULB 约 10 分钟

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

分类

题目描述

✅ 1008. 前序遍历构造二叉搜索树

题意分析

给定一棵二叉搜索树的前序遍历结果，要求把这棵树原样还原出来并返回根节点。题目额外保证输入一定是某棵合法二叉搜索树的前序序列，所以不必做合法性校验，只需要专心还原。

通常「只给一种遍历序列」是无法唯一确定一棵二叉树的，因为同一个前序序列可以对应许多不同形状的树。但这里多了「二叉搜索树」这个限制，它等价于免费提供了一份中序序列——把前序数组排序就是中序。有了前序加中序，树的形状就唯一确定了，这正是题目敢只给一个数组的底气所在。

约束里还有两条值得注意：节点数不超过 100，取值范围在 1 到 1000 之间且互不相同。规模小意味着 $O(n^2)$ 也能过，但不重复这一点更关键，它保证了「小于根」和「大于根」这两类节点之间没有等值的模糊地带，划分左右子树时不会出现歧义。

边界方面，数组至少含一个元素，所以不会出现空树；由于值有上限，根节点的可行取值范围可以用一个足够大的哨兵来表示上界。

解法：递归 + 上界

核心思路

最直白的做法是：取数组首元素当根，然后从第二个元素开始线性扫描，找到第一个大于根的位置作为分界点，左边整段递归建左子树，右边整段递归建右子树。这个思路完全正确，但每一层都要重新扫描一遍自己的区间来找分界点，退化成链状树（比如输入严格递增）时，扫描次数会叠加成 $O(n^2)$。瓶颈就在这个反复的「找分界点」上。

换个角度观察：前序遍历的顺序是根、左子树、右子树，也就是说数组本身已经按访问顺序排好了，我们其实是在从左到右一个一个地消费元素。真正需要判断的不是「分界点在哪」，而是「当前这个元素还属不属于我正在构建的这棵子树」。而二叉搜索树的性质恰好能回答这个问题：任何一棵子树里的所有值，都被它在树中的位置限定在一个开区间内。

于是定义递归函数 build(bound)，它的语义是：从当前全局下标 idx 出发，尽可能多地消费元素，构建出一棵所有节点值都严格小于 bound 的子树，并返回它的根；构建结束时 idx 恰好停在第一个不小于 bound 的元素上（或数组末尾）。这个约定就是整个算法的不变量。

有了它，划分左右子树就不再需要扫描：建完值为 val 的节点后，左子树里的值必须小于 val，所以递归调用 build(val)；左子树自己会在遇到第一个大于 val 的元素时停下来，那个元素正是右子树的根，而右子树只需继承父节点原本的上界 bound。每个元素只被读取和消费一次，$O(n^2)$ 就此降为 $O(n)$。

解题步骤

第一步，用一个成员变量 idx 作为全局游标，初值为 0。之所以用全局游标而不是给每层递归传区间端点，是因为前序遍历天然是单向顺序消费，游标只增不减，把它做成共享状态可以让「上一层停在哪、下一层就从哪继续」这件事自动成立，省去了计算子区间边界的麻烦。Go 版本没有成员变量可用，就改成传递一个 *int 指针，效果完全一样。

第二步，入口调用 build(preorder, Integer.MAX_VALUE)。根节点没有任何祖先约束，它的上界是正无穷，用整型最大值当哨兵即可；因为题目保证节点值不超过 1000，这个哨兵永远不会被真实值触及。Go 里对应写成 1<<31-1，即 2147483647。

第三步，在 build 开头写终止条件：idx == preorder.length 或者 preorder[idx] > bound 时返回 null。前半句处理数组耗尽的情况，必须写在前面，否则后半句会直接下标越界；后半句是核心判断——当前元素超出了本子树允许的取值上界，说明它不属于这里，应该由某个祖先来接管，于是本子树到此为止，返回空。注意这里不消费 idx，游标原地不动，这样上层才能重新看到同一个元素。

第四步，读取 val = preorder[idx++] 并新建节点。读取和自增合并成一步，保证每个元素只被消费一次，也保证游标在进入子递归之前就已经前移，不会形成死循环。

第五步，递归构建左子树 node.left = build(preorder, val)。上界传 val 而不是 bound，是因为左子树里的每个值都必须严格小于当前根；同时这个更紧的上界会让左子树在遇到第一个大于 val 的元素时自动收手。

第六步，递归构建右子树 node.right = build(preorder, bound)。上界传回父节点给的 bound，因为右子树只需要大于当前根（这一点由「左子树已经把所有小于 val 的元素消费完了」隐式保证），而它的上界仍然由更外层的祖先决定。左右两次递归的先后顺序不能调换，前序序列的物理顺序就是先左后右。

第七步，返回 node。递归回溯时每一层都把自己的子树根交还给上层，最终入口那一层返回的就是整棵树的根。

以 preorder = [8, 5, 1, 7, 10, 12] 走一遍：idx = 0，入口 build(bound = MAX)，读到 8，建根节点，idx = 1。构建 8 的左子树 build(5的位置, bound = 8)：读到 5，idx = 2，建节点 5；再构建 5 的左子树 build(bound = 5)，读到 1 小于 5，建节点 1，idx = 3，节点 1 的左子树 build(bound = 1) 看到 7 大于 1 立刻返回空，右子树 build(bound = 5) 看到 7 大于 5 也返回空，于是节点 1 是叶子并返回；回到节点 5，构建其右子树 build(bound = 8)，读到 7 小于 8，建节点 7，idx = 4，节点 7 的左右子树分别以上界 7 和 8 去看 10，都因超界返回空，节点 7 成为叶子；节点 5 完工返回，此时 8 的左子树是 5(1, 7)。回到根 8，构建右子树 build(bound = MAX)，读到 10，建节点 10，idx = 5，节点 10 的左子树 build(bound = 10) 看到 12 大于 10 返回空，右子树 build(bound = MAX) 读到 12，建叶子节点 12，idx = 6，其左右递归都因数组耗尽返回空。最终得到根为 8、左子树 5(1, 7)、右子树 10(null, 12) 的树，与原题答案一致，且六个元素每个只被读取消费了一次。

代码实现

class Solution {
    // 使用全局索引按序读取，递归构建子树并传入上界限制。
    private int idx = 0;

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

    private TreeNode build(int[] preorder, int bound) {
        if (idx == preorder.length || preorder[idx] > bound) {
            return null;
        }

        int val = preorder[idx++];
        TreeNode node = new TreeNode(val);

        node.left = build(preorder, val);
        node.right = build(preorder, bound);

        return node;
    }
}

func bstFromPreorder(preorder []int) *TreeNode {
    // 使用全局索引按序读取，递归构建子树并传入上界限制。
    idx := 0
    return build(preorder, &idx, 1<<31-1)
}

func build(preorder []int, idx *int, bound int) *TreeNode {
    if *idx == len(preorder) || preorder[*idx] > bound {
        return nil
    }

    val := preorder[*idx]
    *idx += 1

    node := &TreeNode{Val: val}
    node.Left = build(preorder, idx, val)
    node.Right = build(preorder, idx, bound)

    return node
}

复杂度分析

时间复杂度：$O(n)$，其中 n 为节点数。游标 idx 只增不减且每个元素恰好被消费一次，其余递归调用要么建出一个新节点、要么因超界立即返回，两类调用的总次数都与节点数成正比。

空间复杂度：$O(n)$。算法本身只用了一个游标变量，但递归深度等于树高，最坏情况下输入是严格递增或递减序列，树退化成一条链，调用栈会压到 n 层；平衡时则是 $O(\log n)$。返回的树本身是结果，不计入额外空间。

关键点总结

一种遍历序列不足以定树，除非题目补上了额外结构：二叉搜索树等价于「中序有序」，前序加隐含中序才让答案唯一，看到「只给一个数组还要建树」就先去找这个隐藏条件。

用取值上下界代替区间端点：树形递归里，与其反复扫描寻找分界位置，不如给每层传一个合法取值范围，让越界自动充当子树的终止信号，这是把 $O(n^2)$ 压到 $O(n)$ 的通用套路。

全局游标要配一个明确的契约：必须能一句话说清「函数返回时游标停在哪」，否则左右子树的衔接就会变成靠试出来的玄学，这个契约也是向面试官证明正确性的抓手。

终止条件里数组越界判断必须排在取值判断之前：这类短路顺序是共享游标写法的固有风险点，写的时候要有意识地留意。

面试视角：先说「首元素为根、扫描找分界、两侧递归」的朴素解法并给出退化成链时的 $O(n^2)$，再引出上界递归的 $O(n)$ 写法；如果面试官继续追问，可以补充用单调栈迭代实现同样效果，或者「排序得到中序后套用 105 题模板」这条思路，说明三者的取舍。

易错点总结

把 idx 声明成 build 的局部变量：preorder = [8, 5, 1] 时每层递归都从 0 开始读，根节点 8 被反复创建，程序陷入无限递归直至栈溢出。

终止条件写成 preorder[idx] > bound || idx == preorder.length：preorder = [8] 建完根节点后 idx 已到末尾，再访问 preorder[1] 直接数组越界。

超界返回前误把 idx 自增：preorder = [8, 10] 时构建 8 的左子树看到 10 超界，如果顺手把游标推过去，右子树就再也读不到 10，最终丢节点，只返回一个孤立的 8。

左子树的上界误传 bound：preorder = [8, 5, 10] 时左子树会把 10 也吞进去挂在 5 的右侧，建出的树中序为 5, 10, 8，不再有序。

右子树的上界误传 val：preorder = [8, 5, 10] 时构建右子树的上界变成 8，10 立刻超界返回空，节点 10 被整个丢弃。

左右递归顺序写反：preorder = [8, 5, 10] 先建右子树会把 5 当成 8 的右孩子，10 又被挂到别处，树形完全错乱。

初始上界传成 1000 或某个「够大」的具体值：如果题目放宽到允许值等于 1000，preorder = [1000] 会因 1000 > 1000 不成立而侥幸通过，但换成上界值本身出现时就会漏节点，用类型最大值当哨兵更稳妥。

在 Go 里把 idx 按值传进递归：preorder = [8, 5, 1] 时子递归对游标的推进无法回传给父调用，父调用会重新读到已经用过的元素，建出重复节点。

判断条件写成 preorder[idx] >= bound：由于左子树的上界正是父节点的值，而题目保证值互不相同，这个写法在本题恰好也对，但一旦题目允许重复值，preorder = [8, 8] 就会把第二个 8 直接丢掉。

以为空间复杂度是 $O(1)$：忽略了递归栈，面对 preorder = [1, 2, 3, ..., n] 这种严格递增输入，树退化成右链，栈深度就是 n，面试中报 $O(1)$ 会被当场纠正。

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	同样靠上下界递归，但做的是校验而不是构造
105. 从前序与中序遍历序列构造二叉树	中等	显式给出中序，需要哈希表把值映射到中序下标来定分界
106. 从中序与后序遍历序列构造二叉树	中等	后序要从右往左消费，根在末尾，左右递归顺序相应颠倒
108. 将有序数组转换为二叉搜索树	简单	只给中序，需自己取中点造根以保证结果平衡
109. 有序链表转换二叉搜索树	中等	结构换成链表，取中点要靠快慢指针或中序模拟建树
255. 验证二叉搜索树的前序遍历序列	中等	输入形式相同但只判合法性，经典解法是单调栈维护下界
331. 验证二叉树的前序序列化	中等	用空指针占位符标记结构，靠槽位计数判断序列是否自洽
449. 序列化和反序列化二叉搜索树	中等	反序列化正是本题，考点扩展到如何设计最紧凑的序列化格式
654. 最大二叉树	中等	分界依据从取值范围换成区间最大值，可用单调栈线性构造
889. 从前序与后序遍历序列构造二叉树	中等	前序加后序无法唯一确定树，需要理解答案不唯一的原因
剑指 Offer 33. 二叉搜索树的后序遍历序列	中等	换成后序序列的合法性判定，根在末尾且需倒序划分左右子树