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

约 4 分钟
文章信息 7 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 美团 虾皮
标签
数组 树 二叉树 栈 二叉搜索树 单调栈

题目描述

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

image-20260928225338754

image-20260928225338755

image-20260928225338756

题意分析

根据二叉搜索树的前序遍历构造树并返回根节点。前序顺序是根、左子树、右子树；二叉搜索树的左侧值更小、右侧值更大。题目保证数组中的值互不相同，并且输入一定能对应一棵合法二叉搜索树。

解法：递归 + 上界

核心思路

[!blue]

用共享游标 idx 指向前序数组中第一个尚未使用的值，build(bound) 构造当前子树，bound 是祖先对这棵子树施加的数值上界。前序保证子树的根最先出现，所以只需判断 preorder[idx] 是否还能放进这里。

若数组已经用完，或当前值超过 bound，就返回空节点，且不能移动游标：这个值可能属于某个祖先的右子树。否则取出当前值 val 并推进 idx，将它作为根，先用更严格的上界 val 构造左子树，再用原来的 bound 构造右子树。

这里只传上界，是因为输入保证合法。按前序顺序建完左子树后，接下来的右子树节点必然大于根；更早祖先带来的下界也由合法的遍历顺序保证。因此不必再传下界，也不必反复扫描寻找左右子树的分割点。该方法用于构造合法输入，不能直接当作前序序列合法性验证器。

解题步骤

  1. 将 idx 置为 0，用足够大的初始上界开始构造整棵树。
  2. idx 已到数组末尾或当前值超界时，返回空节点，不消费这个值。
  3. 取 preorder[idx] 创建节点，并令 idx++。
  4. 先以上界 val 构造左子树，再以上界 bound 构造右子树。
  5. 返回当前根节点，所有递归共享同一个消费位置。

代码实现

class Solution {
    private int idx = 0;

    public TreeNode bstFromPreorder(int[] preorder) {
        // 每次重建都从新数组的首位开始消费。
        idx = 0;

        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 为数组长度；每个节点只创建一次，每次创建只产生两个子调用。
  • 空间复杂度：$O(h)$，不计输出树，只计高度为 h 的递归栈；最坏链状树为 $O(n)$。

关键点总结

[!green]

  • 超界意味着不属于这里，不能顺便移动游标。
  • 所有递归共享消费进度，Java 成员状态每次入口重置。
  • 左子树收紧上界，右子树恢复到当前子树原本的上界，仍然受更早祖先约束。

易错点总结

[!yellow]

  • 右子树仍传根值作上界，会拒绝合法较大节点。
  • 左右递归顺序颠倒，会破坏前序消费顺序。
  • Go 游标按值各自修改，父层无法看到子树已经消费的元素。

相似题目

题目 难度 关联与区别
255. 验证二叉搜索树的前序遍历序列 中等 验证BST前序与构造都可利用范围上下界或单调栈维护已经进入右子树后的限制。
105. 从前序与中序遍历序列构造二叉树 中等 普通树还需中序划分左右子树，本题BST值域规则已提供这个划分依据。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/49875407
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！