Hot 100 --- 从前序与中序遍历序列构造二叉树

本文概览：本文以LeetCode题目"从前序与中序遍历序列构造二叉树"为例，详细讲解如何把"分治构造"的想法转化为递归代码，重点说明递归的出口和参数传递

一、题目

![[从前序与中序遍历序列构造二叉树题目.png]]

二、题目分析

这题的难点不是思路本身——给你前序和中序序列，手动画出一棵二叉树大多数人都会。真正的难点是把这套手动操作的过程精确地转化成代码。手动操作时，每一步"找根节点、切左右子树"都很自然，但写代码时你必须回答：递归的出口是什么？每一轮要传哪些参数？子树的范围怎么从上一轮推导出来？只要有一个环节模糊，代码就写不出来

思路概览

Java 实现代码如下

publicTreeNodebuildTree(int[]preorder,int[]inorder){if(preorder.length==0||inorder.length==0){returnnull;}// 构建映射表,记录中序遍历中每个节点的索引,方便后续快速定位Map<Integer,Integer>inMap=newHashMap<>();for(inti=0;i<inorder.length;i++){inMap.put(inorder[i],i);}// 递归构建树returnhelper(preorder,0,preorder.length-1,inorder,0,inorder.length-1,inMap);}privateTreeNodehelper(int[]preorder,intpreStart,intpreEnd,int[]inorder,intinStart,intinEnd,Map<Integer,Integer>inMap){// 递归终止条件,说明没有节点了if(preStart>preEnd||inStart>inEnd){returnnull;}// 构建根节点TreeNoderoot=newTreeNode(preorder[preStart]);// 从中序遍历的索引表中定位到根节点的索引intinRoot=inMap.get(root.val);// 计算左子树的节点数量intleftSize=inRoot-inStart;// 递归构建左子树root.left=helper(preorder,preStart+1,preStart+leftSize,inorder,inStart,inRoot-1,inMap);// 递归构建右子树root.right=helper(preorder,preStart+leftSize+1,preEnd,inorder,inRoot+1,inEnd,inMap);returnroot;}

思路简要说明

核心是分治：每轮从前序序列中取出根节点，再从中序序列中找到根的位置把左右子树分开，然后对左右子树分别递归做同样的事

• 每轮的操作：取前序第一个值作为根 → 在中序中定位根 → 根左边是左子树，根右边是右子树 → 用左子树节点数在前序中切出左右子树的序列 → 递归
• 递归出口：当前范围为空（preStart > preEnd或inStart > inEnd），说明没有节点了
• 递归参数：前序数组 + 前序起止索引 + 中序数组 + 中序起止索引，共 6 个范围参数
• 优化：用哈希表inMap记录中序遍历值到索引的映射，把每次查找从 O(n) 降到 O(1)

三、思路详解

构建过程的完整推演

前序遍历的结构是[根][左子树][右子树]，中序遍历的结构是[左子树][根][右子树]。这两个结构就是构建的依据

用一个具体例子来推演整个过程：

前序遍历：[3, 9, 20, 15, 7] 中序遍历：[9, 3, 15, 20, 7]

第 1 轮：处理整棵树

前序序列[3, 9, 20, 15, 7]，中序序列[9, 3, 15, 20, 7]

① 前序第一个值是3，所以根节点 = 3

② 在中序序列中找 3 的位置：[9, |3|, 15, 20, 7]，索引 = 1

③ 根据中序的结构[左][根][右]，3 的左边[9]是左子树，3 的右边[15, 20, 7]是右子树。所以左子树有1个节点，右子树有3个节点

④ 根据前序的结构[根][左][右]，根之后的前 1 个值是左子树，剩余的是右子树：

前序：[3] [9] [20, 15, 7] 根 左 右 中序：[9] [3] [15, 20, 7] 左 根 右

到此，根节点 3 构建好了，接下来要分别构建左子树[9]和右子树[20,15,7]

第 2 轮：构建左子树（3 的左孩子）

前序左子树[9]，中序左子树[9]

① 前序第一个值是9，所以这个子树的根节点 = 9

② 在中序中找 9：[|9|]，索引 = 0（相对当前范围）

③ 9 的左边为空，9 的右边为空 → 没有子树了

前序：[9] 根 中序：[9] 根

节点 9 是个叶子。3 的左孩子 = 9，左子树构建完毕

第 3 轮：构建右子树（3 的右孩子）

前序右子树[20, 15, 7]，中序右子树[15, 20, 7]

① 前序第一个值是20，所以这个子树的根节点 = 20

② 在中序中找 20：[15, |20|, 7]，索引 = 1（相对当前范围）

③ 20 的左边[15]是左子树，20 的右边[7]是右子树。左子树有1个节点，右子树有1个节点

④ 前序中根之后前 1 个是左子树，剩余是右子树：

前序：[20] [15] [7] 根 左 右 中序：[15] [20] [7] 左 根 右

根节点 20 构建好了，继续构建它的左右子树

第 4 轮：构建 20 的左孩子

前序[15]，中序[15]

前序第一个值是15，中序中 15 左右都为空 → 叶子节点。20 的左孩子 = 15

第 5 轮：构建 20 的右孩子

前序[7]，中序[7]

前序第一个值是7，中序中 7 左右都为空 → 叶子节点。20 的右孩子 = 7

构建完成：

3 / \ 9 20 / \ 15 7

整个过程的关键：每一轮都能从上一轮的范围内确定"根节点是谁"和"左右子树各占多少"，然后把这个范围传给下一轮。这就是分治的核心——大问题拆成同结构的小问题

把思路变成递归

现在思路很清楚了，但怎么写成代码？让我们套用之前讲的"递归三步法"。

1. 找出口

出口就是"没有节点可构造"。当某个范围（前序范围或中序范围）为空时，说明这一轮没有节点，返回null

if (preStart > preEnd || inStart > inEnd) { return null; }

2. 找当前节点要做什么

构造根节点。根节点就是当前前序范围的第一项：

TreeNode root = new TreeNode(preorder[preStart]);

3. 找下一轮的参数

这是最关键的一步——下一轮要传什么参数，才能让子节点和当前节点做一样的事？

观察我们的思路：每轮要做的事是"给我前序的一段和中序的一段，我构造出这棵子树"。所以每轮都需要：

• 前序遍历数组+前序遍历的起止索引（preStart, preEnd）
• 中序遍历数组+中序遍历的起止索引（inStart, inEnd）

4. 怎么切出左右子树的范围

假设当前是这一轮：

前序：[..., preStart, ..., ..., preEnd] ↑ 根节点 中序：[..., inStart, ..., ..., inEnd] ↑ inRoot 根节点索引

我们已经在中序中找到inRoot，接下来要算左子树的节点数：

int leftSize = inRoot - inStart;

左子树的参数：

• 前序：从preStart+1到preStart+leftSize（根节点后面leftSize个就是左子树）
• 中序：从inStart到inRoot-1（根节点左边就是左子树）

右子树的参数：

• 前序：从preStart+leftSize+1到preEnd（左子树之后就是右子树）
• 中序：从inRoot+1到inEnd（根节点右边就是右子树）

把这些代入递归调用即可：

root.left=helper(preorder,preStart+1,preStart+leftSize,inorder,inStart,inRoot-1,inMap);root.right=helper(preorder,preStart+leftSize+1,preEnd,inorder,inRoot+1,inEnd,inMap);

用图来理解范围切分

把第一轮的所有范围画出来，方便看递归的传参：

前序遍历：[3, 9, 20, 15, 7] 索引： 0 1 2 3 4 中序遍历：[9, 3, 15, 20, 7] 索引： 0 1 2 3 4 哈希表 inMap：{9→0, 3→1, 15→2, 20→3, 7→4}

第一轮helper(0, 4, 0, 4)：

前序范围：preStart=0, preEnd=4 → [3, 9, 20, 15, 7] 中序范围：inStart=0, inEnd=4 → [9, 3, 15, 20, 7] ↑ inStart ↑ inEnd ↑ inRoot=1（根节点3的索引） 根节点 = preorder[0] = 3 leftSize = inRoot - inStart = 1 - 0 = 1

切分：

前序左：[preStart+1, preStart+leftSize] = [1, 1] → [9] 前序右：[preStart+leftSize+1, preEnd] = [2, 4] → [20,15,7] 中序左：[inStart, inRoot-1] = [0, 0] → [9] 中序右：[inRoot+1, inEnd] = [2, 4] → [15,20,7]

第二轮（构造节点 9）helper(1, 1, 0, 0)：

前序范围：preStart=1, preEnd=1 → [9] 中序范围：inStart=0, inEnd=0 → [9] inRoot=0（左子树 9 的索引） 根节点 = preorder[1] = 9 leftSize = 0 - 0 = 0

切分：

前序左：[2, 1] → preStart > preEnd，出口，返回 null 前序右：[2, 1] → preStart > preEnd，出口，返回 null

节点 9 是个叶子

第三轮（构造节点 20）helper(2, 4, 2, 4)：

前序范围：preStart=2, preEnd=4 → [20, 15, 7] 中序范围：inStart=2, inEnd=4 → [15, 20, 7] inRoot=3（节点20的索引） 根节点 = preorder[2] = 20 leftSize = 3 - 2 = 1

切分：

前序左：[3, 3] → [15] 前序右：[4, 4] → [7] 中序左：[2, 2] → [15] 中序右：[4, 4] → [7]

继续递归构造 15 和 7，都是叶子

构造完成：

3 / \ 9 20 / \ 15 7

优化：用哈希表加速中序遍历的查找

每轮递归都需要在中序遍历中找到根节点的索引。如果每次都在中序数组中线性查找，时间复杂度是 O(n)，n 个节点就要 O(n²) 总时间

优化方法：在调用helper之前，先用一次遍历构建哈希表inMap，把每个节点的值映射到它在数组中的索引。这样每轮查找索引的时间就是 O(1)，总时间复杂度降到 O(n)

Map<Integer,Integer>inMap=newHashMap<>();for(inti=0;i<inorder.length;i++){inMap.put(inorder[i],i);}

后续查找时直接inMap.get(root.val)即可

复杂度分析

• 时间复杂度：O(n)，每个节点被处理一次，加上哈希表的 O(n) 初始化
• 空间复杂度：O(n)，哈希表 O(n) + 递归栈 O(h)，h 为树高，最坏 O(n)