LeetCode 105. 从前序与中序遍历序列构造二叉树

2026-06-29 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 中等已解决需加强 100-200 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴华为拼多多虾皮小红书作业帮 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 105. 从前序与中序遍历序列构造二叉树

题意分析

给出同一棵二叉树的前序遍历和中序遍历两个数组，要求还原并返回这棵树本身。产出是一棵完整的树结构，不是某个数值——任何一个节点挂错位置、挂错左右，都算错，所以每一步「谁是根、谁归左、谁归右」都必须有确定依据。

两个序列各自携带的信息不同。前序按「根 → 左 → 右」的顺序访问，所以前序的第一个元素一定是整棵树的根，这是拿到输入后唯一能立刻确定的节点。中序按「左 → 根 → 右」的顺序访问，所以只要知道根是谁，中序里根左边的一整段就恰好是左子树的全部节点、右边的一整段就是右子树的全部节点。单看任何一个序列都还原不出唯一的树，两个序列拼起来信息才完整。

约束里最关键的信号是「树中没有重复元素」。没有重复，值和位置才一一对应，才能按「根的值」在中序数组里唯一地定位它的下标——这正是能用哈希表预存「值 → 中序下标」的前提。如果允许重复值，同一个值会对应多个候选切分点，这套还原逻辑本身就不成立。另外 n 最多 3000，平方级做法也能通过，但这个规模挡不住面试官对线性做法的期待。

边界情形：序列长度为 1 时应返回单节点树；树可能退化成一条只有左孩子（或只有右孩子）的链，此时每一层切分出的另一侧都是空序列，还原过程必须能自然地处理空区间并返回空指针。

解法：递归切分前序与中序区间

核心思路

前序遍历的第一个元素是根，中序遍历中根的左侧属于左子树、右侧属于右子树。先建立「节点值到中序下标」的映射，再按区间递归建树，避免反复扫描和复制数组。

对当前中序区间 [inLeft, inRight]，根在中序中的位置决定左子树大小，也就确定了左右子树在前序中的根下标。

解题步骤

遍历中序数组，建立节点值到下标的哈希表。

前序区间首元素作为当前根节点。

根据根的中序下标计算左子树大小，递归构造左右子树。

中序区间为空时返回空节点。

代码实现

class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return build(preorder, 0, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preRoot, int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }

        int rootVal = preorder[preRoot];
        TreeNode root = new TreeNode(rootVal);
        int rootIdx = indexMap.get(rootVal);
        int leftSize = rootIdx - inLeft;

        root.left = build(preorder, preRoot + 1, inLeft, rootIdx - 1);
        root.right = build(preorder, preRoot + leftSize + 1, rootIdx + 1, inRight);
        return root;
    }
}

func buildTree(preorder []int, inorder []int) *TreeNode {
    indexMap := make(map[int]int)
    for i, num := range inorder {
        indexMap[num] = i
    }

    var build func(preRoot, inLeft, inRight int) *TreeNode
    build = func(preRoot, inLeft, inRight int) *TreeNode {
        if inLeft > inRight {
            return nil
        }

        rootVal := preorder[preRoot]
        root := &TreeNode{Val: rootVal}
        rootIdx := indexMap[rootVal]
        leftSize := rootIdx - inLeft

        root.Left = build(preRoot+1, inLeft, rootIdx-1)
        root.Right = build(preRoot+leftSize+1, rootIdx+1, inRight)
        return root
    }

    return build(0, 0, len(inorder)-1)
}

复杂度分析

时间复杂度：$O(n)$，每个节点只创建一次，根位置通过哈希表查询。

空间复杂度：$O(n)$，哈希表占 $O(n)$，递归栈最坏占 $O(n)$。

关键点总结

前序负责确定根，中序负责划分左右子树。

哈希表将中序下标查询降为 $O(1)$，前提是节点值互不相同。

递归只传区间下标，不复制子数组。

易错点总结

leftSize 应为 rootIdx - inLeft，不要混用前序和中序下标。

右子树前序根下标应为 preRoot + leftSize + 1。

空区间条件是 inLeft > inRight，不能把单节点区间判空。

Go 的递归闭包需要先声明函数变量，再进行赋值。

相似题目

题目	难度	考察点
106. 从中序与后序遍历序列构造二叉树	中等	本题的镜像：根改从后序区间末尾取，切分逻辑对称，是最高频的对照追问
剑指 Offer 07. 重建二叉树	中等	与本题同题异名，适合原样复写一遍模板检验熟练度
889. 根据前序和后序遍历构造二叉树	中等	缺少中序导致树不唯一，需自行约定单孩子归左，理解「为什么必须有中序」
108. 将有序数组转换为二叉搜索树	简单	有序数组即中序序列，根不再由前序给出而是取区间中点以保证平衡
109. 有序链表转换二叉搜索树	中等	输入换成链表无法随机访问，找中点要靠快慢指针或全局指针中序构建
面试题 04.02. 最小高度树	简单	与 108 同型，重点在论证「取中点」为何能使高度最小
1008. 前序遍历构造二叉搜索树	中等	只给前序，靠 BST 的值域上下界代替中序完成切分
654. 最大二叉树	中等	同样的区间切分骨架，但根改为区间最大值，可进一步用单调栈做到线性