本文概览本文以LeetCode题目从前序与中序遍历序列构造二叉树为例详细讲解如何把分治构造的想法转化为递归代码重点说明递归的出口和参数传递一、题目![[从前序与中序遍历序列构造二叉树题目.png]]二、题目分析这题的难点不是思路本身——给你前序和中序序列手动画出一棵二叉树大多数人都会。真正的难点是把这套手动操作的过程精确地转化成代码。手动操作时每一步找根节点、切左右子树都很自然但写代码时你必须回答递归的出口是什么每一轮要传哪些参数子树的范围怎么从上一轮推导出来只要有一个环节模糊代码就写不出来思路概览Java 实现代码如下publicTreeNodebuildTree(int[]preorder,int[]inorder){if(preorder.length0||inorder.length0){returnnull;}// 构建映射表,记录中序遍历中每个节点的索引,方便后续快速定位MapInteger,IntegerinMapnewHashMap();for(inti0;iinorder.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,MapInteger,IntegerinMap){// 递归终止条件,说明没有节点了if(preStartpreEnd||inStartinEnd){returnnull;}// 构建根节点TreeNoderootnewTreeNode(preorder[preStart]);// 从中序遍历的索引表中定位到根节点的索引intinRootinMap.get(root.val);// 计算左子树的节点数量intleftSizeinRoot-inStart;// 递归构建左子树root.lefthelper(preorder,preStart1,preStartleftSize,inorder,inStart,inRoot-1,inMap);// 递归构建右子树root.righthelper(preorder,preStartleftSize1,preEnd,inorder,inRoot1,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. 找出口出口就是没有节点可构造。当某个范围前序范围或中序范围为空时说明这一轮没有节点返回nullif (preStart preEnd || inStart inEnd) { return null; }2. 找当前节点要做什么构造根节点。根节点就是当前前序范围的第一项TreeNode root new TreeNode(preorder[preStart]);3. 找下一轮的参数这是最关键的一步——下一轮要传什么参数才能让子节点和当前节点做一样的事观察我们的思路每轮要做的事是给我前序的一段和中序的一段我构造出这棵子树。所以每轮都需要前序遍历数组前序遍历的起止索引preStart, preEnd中序遍历数组中序遍历的起止索引inStart, inEnd4. 怎么切出左右子树的范围假设当前是这一轮前序[..., preStart, ..., ..., preEnd] ↑ 根节点 中序[..., inStart, ..., ..., inEnd] ↑ inRoot 根节点索引我们已经在中序中找到inRoot接下来要算左子树的节点数int leftSize inRoot - inStart;左子树的参数前序从preStart1到preStartleftSize根节点后面leftSize个就是左子树中序从inStart到inRoot-1根节点左边就是左子树右子树的参数前序从preStartleftSize1到preEnd左子树之后就是右子树中序从inRoot1到inEnd根节点右边就是右子树把这些代入递归调用即可root.lefthelper(preorder,preStart1,preStartleftSize,inorder,inStart,inRoot-1,inMap);root.righthelper(preorder,preStartleftSize1,preEnd,inorder,inRoot1,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)前序范围preStart0, preEnd4 → [3, 9, 20, 15, 7] 中序范围inStart0, inEnd4 → [9, 3, 15, 20, 7] ↑ inStart ↑ inEnd ↑ inRoot1根节点3的索引 根节点 preorder[0] 3 leftSize inRoot - inStart 1 - 0 1切分前序左[preStart1, preStartleftSize] [1, 1] → [9] 前序右[preStartleftSize1, preEnd] [2, 4] → [20,15,7] 中序左[inStart, inRoot-1] [0, 0] → [9] 中序右[inRoot1, inEnd] [2, 4] → [15,20,7]第二轮构造节点 9helper(1, 1, 0, 0)前序范围preStart1, preEnd1 → [9] 中序范围inStart0, inEnd0 → [9] inRoot0左子树 9 的索引 根节点 preorder[1] 9 leftSize 0 - 0 0切分前序左[2, 1] → preStart preEnd出口返回 null 前序右[2, 1] → preStart preEnd出口返回 null节点 9 是个叶子第三轮构造节点 20helper(2, 4, 2, 4)前序范围preStart2, preEnd4 → [20, 15, 7] 中序范围inStart2, inEnd4 → [15, 20, 7] inRoot3节点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)MapInteger,IntegerinMapnewHashMap();for(inti0;iinorder.length;i){inMap.put(inorder[i],i);}后续查找时直接inMap.get(root.val)即可复杂度分析时间复杂度O(n)每个节点被处理一次加上哈希表的 O(n) 初始化空间复杂度O(n)哈希表 O(n) 递归栈 O(h)h 为树高最坏 O(n)