本文概览：本文以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)
