题目描述
思路解析
一句话答案：LeetCode 105 从前序与中序遍历序列构造二叉树用分治递归：preorder 每段的第一个元素必是该子树的根，到 inorder 里找到根的位置即可把左右子树的节点劈成两半，再对两半递归同样的操作；配一张「值到下标」的哈希表把找根降到 O(1)，整体时间 O(n)、空间 O(n)。
前序和中序各自透露了什么信息
前序遍历的顺序是「根、左、右」，所以 preorder 里任何一棵子树对应的连续段，第一个元素一定是这棵子树的根——根的信息全在前序里。中序遍历的顺序是「左、根、右」，所以在 inorder 里一旦定位到根，它左边的所有值恰好组成左子树、右边的所有值恰好组成右子树——左右怎么划分的信息全在中序里。题目保证节点值互不相同，这个定位才是唯一的。
单看任何一条序列都重建不出树：前序知道谁是根却不知道左右子树的边界在哪，中序知道相对位置却不知道谁是根。两条拼在一起，信息恰好互补。
为什么这自然长成一个分治递归
拿到根、劈出左右两半之后会发现：剩下的任务「用左子树的前序和中序重建左子树」「用右子树的前序和中序重建右子树」，跟原问题一模一样，只是规模变小了。这正是分治的形状——同一套「取前序段首当根、去中序劈左右」的动作递归地做下去，直到某个中序区间为空，说明这棵子树不存在，返回 None。
preorder 那侧的切分也由中序顺手给出：设根在中序区间里左边有 k 个值，那么前序里紧跟根之后的 k 个元素就是左子树的前序，再往后是右子树的前序。实现时甚至不必显式切前序数组，维护一个全局递增的 pre 指针即可——只要坚持「先建左子树、再建右子树」，指针消费元素的顺序恰好和「根左右」对齐，每次取 preorder[self.pre] 再加一就是当前子树的根。顺序一旦颠倒成先右后左，指针取到的元素就全部错位。
哈希表为什么是复杂度的分水岭
每层递归都要回答「根在 inorder 的哪个位置」。如果每次线性扫描，单次 O(n)，n 个节点就是 O(n²)——链状树会真踩到这个最坏值。预处理一张哈希表 pos 存「值到下标」的映射，定位变成 O(1)，整体回到 O(n)。一次 O(n) 的预处理换掉递归里的重复扫描，是典型的空间换时间。
每一步为什么不会建错
正确性靠两条性质支撑：一是前序段首必为根（前序先访问根），二是中序中根两侧恰为左右子树的全部节点（中序先左后根再右）。归纳地看，只要当前段对应一棵真实子树，取出的根就是对的，劈出的两个中序区间也各自对应一棵真实子树，递归假设它们能被正确重建，拼上根就是正确的整树。区间为空返回 None 作为出口，归纳链条完整。
复杂度与常见翻车点
时间 O(n)：每个节点恰好被构造一次，找根靠哈希是 O(1)。空间 O(n)：哈希表存 n 个映射，加上递归栈 O(h)，h 为树高。
三个高频错误：左子树节点个数应是「根在中序的下标减去区间左端点」，算错则前序左右段全部切歪；先建右再建左会让 pre 指针错位（前面已说）；忘写空区间出口 inL > inR 会无限递归。变式题「中序 + 后序」同理可解——后序是「左右根」，从末尾取根、先建右再建左；而「前序 + 后序」一般不能唯一定树，因为两者都定不出单孩子在左还是在右。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
于是重建变成一个分治：preorder 给你根，inorder 告诉你左右子树各有多少个、分别是哪些节点。按左子树的个数，又能把 preorder 切成左段、右段，对两段递归同样的操作。为了 O(1) 找到根在 inorder 的位置，先用哈希表存「值→下标」。下面逐个节点重建。
准备 · 两条序列：重建之前先摆清两条序列：preorder 的第一个数 3 就是整棵树的根。接下来我们从这个根出发，每一步都「取前序段首当根 → 去中序定位 → 劈出左右区间 → 递归」，让节点一个个落到树上。
定位根 3：取出 preorder 当前段的第一个元素 3，它一定是这棵子树的根。再去 inorder 里找到 3（第 5 位）：它左边的 5 个数（6 8 9 10 11）就是左子树的中序，右边的 3 个数（15 20 7）就是右子树的中序。根定，左右区间也就劈开了。
落子 3：把根 3 安放到树上。知道了左子树有 5 个节点，就能在 preorder 里切出左段（9 8 6 10 11）和右段（20 15 7）：紧跟根之后的 5 个是左子树前序，再往后是右子树前序。对这两段递归同样的步骤，整棵树就长出来了。
定位根 9：取出 preorder 当前段的第一个元素 9，它一定是这棵子树的根。再去 inorder 里找到 9（第 2 位）：它左边的 2 个数（6 8）就是左子树的中序，右边的 2 个数（10 11）就是右子树的中序。根定，左右区间也就劈开了。
落子 9：把根 9 安放到树上。知道了左子树有 2 个节点，就能在 preorder 里切出左段（8 6）和右段（10 11）：紧跟根之后的 2 个是左子树前序，再往后是右子树前序。对这两段递归同样的步骤，整棵树就长出来了。
定位根 8：取出 preorder 当前段的第一个元素 8，它一定是这棵子树的根。再去 inorder 里找到 8（第 1 位）：它左边的 1 个数（6）就是左子树的中序，右边的 0 个数（空）就是右子树的中序。根定，左右区间也就劈开了。
落子 8：把根 8 安放到树上。知道了左子树有 1 个节点，就能在 preorder 里切出左段（6）和右段（空）：紧跟根之后的 1 个是左子树前序，再往后是右子树前序。对这两段递归同样的步骤，整棵树就长出来了。
定位根 6：取出 preorder 当前段的第一个元素 6，它一定是这棵子树的根。再去 inorder 里找到 6（第 0 位）：它左边的 0 个数（空）就是左子树的中序，右边的 0 个数（空）就是右子树的中序。根定，左右区间也就劈开了。
落子 6 · 叶子：节点 6 的左右中序都为空，它是叶子，这一支到底了，回到上层继续。
定位根 10：取出 preorder 当前段的第一个元素 10，它一定是这棵子树的根。再去 inorder 里找到 10（第 3 位）：它左边的 0 个数（空）就是左子树的中序，右边的 1 个数（11）就是右子树的中序。根定，左右区间也就劈开了。
落子 10：把根 10 安放到树上。知道了左子树有 0 个节点，就能在 preorder 里切出左段（空）和右段（11）：紧跟根之后的 0 个是左子树前序，再往后是右子树前序。对这两段递归同样的步骤，整棵树就长出来了。
定位根 11：取出 preorder 当前段的第一个元素 11，它一定是这棵子树的根。再去 inorder 里找到 11（第 4 位）：它左边的 0 个数（空）就是左子树的中序，右边的 0 个数（空）就是右子树的中序。根定，左右区间也就劈开了。
落子 11 · 叶子：节点 11 的左右中序都为空，它是叶子，这一支到底了，回到上层继续。
定位根 20：取出 preorder 当前段的第一个元素 20，它一定是这棵子树的根。再去 inorder 里找到 20（第 7 位）：它左边的 1 个数（15）就是左子树的中序，右边的 1 个数（7）就是右子树的中序。根定，左右区间也就劈开了。
落子 20：把根 20 安放到树上。知道了左子树有 1 个节点，就能在 preorder 里切出左段（15）和右段（7）：紧跟根之后的 1 个是左子树前序，再往后是右子树前序。对这两段递归同样的步骤，整棵树就长出来了。
定位根 15：取出 preorder 当前段的第一个元素 15，它一定是这棵子树的根。再去 inorder 里找到 15（第 6 位）：它左边的 0 个数（空）就是左子树的中序，右边的 0 个数（空）就是右子树的中序。根定，左右区间也就劈开了。
落子 15 · 叶子：节点 15 的左右中序都为空，它是叶子，这一支到底了，回到上层继续。
定位根 7：取出 preorder 当前段的第一个元素 7，它一定是这棵子树的根。再去 inorder 里找到 7（第 8 位）：它左边的 0 个数（空）就是左子树的中序，右边的 0 个数（空）就是右子树的中序。根定，左右区间也就劈开了。
落子 7 · 叶子：节点 7 的左右中序都为空，它是叶子，这一支到底了，回到上层继续。
重建完成：9 个节点全部落位，整棵树重建完成。每个节点都来自「前序定根、中序分左右」这一条规则的递归：preorder 决定了访问顺序与每段的根，inorder 决定了每个根两侧子树的大小。两条一维序列，就这样唯一地拼回了一棵树。
边界先想清：preorder 一模一样、只是 inorder 里根的位置不同，左右孩子就反了——再次印证「是中序在决定左右」。
三个高频追问：中序+后序可重建、前序+后序一般不唯一、哈希表是 O(n) 的关键。
参考代码
class Solution { int[] preorder; Map<Integer,Integer> pos = new HashMap<>(); // inorder 值 -> 下标 int pre = 0; // preorder 扫描指针 public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i); return build(0, inorder.length - 1); } private TreeNode build(int inL, int inR) { if (inL > inR) return null; // 空区间 int rootVal = preorder[pre++]; // 前序首元素 = 根 TreeNode root = new TreeNode(rootVal); int k = pos.get(rootVal); // 根在 inorder 的位置 root.left = build(inL, k - 1); // 先建左（前序里先出现） root.right = build(k + 1, inR); // 再建右 return root; }}复杂度
- 时间：O(n)，每个节点恰好构造一次；哈希定位 O(1)
- 空间：O(n)，哈希表 O(n) + 递归栈 O(h)，h 为树高
易错点
面试追问把动画讲成自己的话
追问用中序 + 后序能重建吗？
追问为什么前序 + 后序通常不能唯一确定一棵树？
追问不用哈希表、每次线性找根，复杂度如何？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树中的最大路径和
LeetCode 124 · 困难 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题