企业官网建设流程全解析

训练营的第十六天打卡完成，今天的五道题全在二叉树递归这一个圈子里打转：找左下角的值、路径总和、路径总和 II、从中序与后序遍历构造二叉树、从前序与中序遍历构造二叉树。刷完最大的感受是——递归的难点从来不是“写出来”，而是“写出来之后还能自信地解释每一步为什么这么写”。这篇文章把我今天踩过的坑、推敲过的边界、还有面试时怎么答这类题的思路都整理出来，适合正在刷二叉树递归和回溯的朋友对照参考。

1. 整体设计与思路拆解

1.1 这五道题的定位与递进关系

很多人刷二叉树喜欢按“遍历顺序”分类，前序、中序、后序、层序各刷一遍，然后进入递归做题。但今天的五道题串起来看，更像是用三条主线把二叉树题目重新串了一遍。

第一组是513找树左下角的值，核心是“层序或深度优先如何记录目标节点”的问题。它没有要求你对整棵树做任何修改，只是要求在遍历过程中盯住一个符合条件的节点。第二组是112路径总和和113路径总和 II，这两道题属于“递归+回溯”的经典入口，一个只问“存不存在”，一个要你“把所有路径全拿出来”，完全是一对递进题。第三组是106和105两道构造二叉树题，它们问的是“给定两种遍历序列，能不能把整棵树还原出来”，考察的是对中序、前序、后序三种遍历顺序本质的理解，而不是单纯的遍历代码。

把五道题放在一起看，会发现它们是同一个能力的不同侧面：你能否在一棵树上做递归状态传递；你能否在递归过程中维护和恢复状态；你能否通过序列的区间切分来定位根节点。这三件事几乎覆盖了二叉树递归问题的全部基础场景。今天能把这五道题吃透，后面再遇到“最近公共祖先”“二叉树的最大路径和”这类综合题会轻松不少。

1.2 递归思维的两个基本套路：递推式与回溯式

做今天的题之前，我特意把递归的思考方式重新捋了一下。二叉树递归题基本逃不开两种套路。

第一种是递推式递归。它的典型形态是“当前节点的结果由左右子树的结果算出”，比如求最大深度、求节点个数。这种题的思维模型很直接，你只需要关注当前节点和左右子树的返回值，不用关心整棵树长什么样。513找树左下角的值如果用DFS写法，其实就是这种思路的变体，只不过它不完全依赖返回值，而是通过传递深度和答案引用。

第二种是回溯式递归。它关心的不是“子树返回了什么”，而是“从根到当前节点这条路径上累积了什么信息”，比如112和113。这种题真正的难点在于状态管理：你进入一个子节点之前要做什么，出来之后要恢复什么。很多初学朋友写的路径总和代码找不到全部路径，问题往往不是递归逻辑本身，而是回溯时漏了恢复状态。

构造二叉树两道题则属于递归里更高级的区间分治。它需要你同时掌握前序/中序/后序的遍历特征，再把中序序列划分成左右子树两段，利用递归向下建树。这种题很考验对“区间边界”的敏感度，差一个下标整棵树就建错。刷完今天的题目，我发现自己在这三种套路里切换得越熟练，遇到的二叉树新题就越容易往已知题型上靠。

2. 核心细节解析与实操要点

2.1 找树左下角的值：BFS比DFS更直观

513题要求返回二叉树最后一行的最左边值，注意不是“最左边的叶子节点”，而是“最后一层的最左节点”。题目描述里树的节点值不重复且为整数，所以返回节点值即可。

这道题第一个能想到的思路是层序遍历。用队列做标准的BFS，每次处理一层时记录第一个出队的节点值，遍历完所有层之后，最后一次记录的节点值就是答案。因为层序天然是一层一层从左边到右边扫的，所以记录每层第一个节点，最后留下的必是最后一层的最左节点。

也可以用DFS。思路是维护一个全局最大深度，在深度优先递归时优先往左走。每到达一个新深度，如果是第一次到达，就更新答案。因为总是先访问左边，所以每个深度的第一个被访问到的节点一定是最左边的节点，到树的最深层时，那个记录值就是左下角的值。这个写法和“找二叉树最深层的最左节点”就很吻合。

两种写法复杂度都是O(n)，BFS消耗队列空间，DFS消耗递归栈空间。面试如果被问到这道题，我更建议先答BFS，因为实现简单、不容易在深度记录上翻车；答完再补充DFS版本，还能展示自己对两种遍历方式的理解。

DFS版本有个容易踩的点：深度判断必须严格大于历史最大深度时才更新，不能用“等于当前最大深度也更新”。否则每一层最右边的节点可能会覆盖掉之前记录的最左值，导致答案错误。我第一次写就犯了这个问题，后面调试了半天才发现是更新条件写松了。

2.2 路径总和与路径总和 II：从“有没有”到“全部拿出来”

112路径总和要求判断是否存在一条从根到叶子的路径，使路径上所有节点值之和等于目标值。题目明确限定“叶子节点”是左右子节点都为空的节点，所以判断终止时不能只看当前节点为空。

递归的思路可以写成目标值递减的形式：每走到一个节点，用targetSum减去当前节点值，如果当前节点是叶子且递减后的值等于0，就找到了目标路径；否则继续往左右子节点递归，注意递归时传入的是递减后的值。

113路径总和 II是112的进阶版，要求把所有满足条件的路径收集起来。这里核心是回溯。用一个path列表记录当前路径上的节点，走到叶子时判断路径和是否满足条件，满足就把path的副本加入结果集。关键步骤是在递归返回父节点之前，把当前节点从path中移除，恢复现场。

我见过很多人在113上犯的典型错误有两个。第一个是没有对path做拷贝，直接把path对象加入结果集，结果后面回溯时path被修改，之前保存的路径全部变成最后的状态。第二个是漏了回溯，导致一条路径被无限继承到别的分支里，最终结果里出现大量乱七八糟的路径。解决办法也很简单：向结果集添加new ArrayList<>(path)，并且保证递归出口处有一次path.remove。

这两道题教会我的核心是：“判断存在”可以只靠返回值，而“收集路径”必须依赖外部容器和状态恢复。前者是递归的返回值建模，后者是回溯的状态建模，二者不要混着写。

2.3 中序+后序 / 前序+中序构造二叉树：分治定位的通用规律

106题给出中序遍历和后序遍历序列，要求还原二叉树。105题给出前序遍历和中序遍历序列，要求还原二叉树。这两道题是同一类问题，都是利用中序序列配合另一种遍历序列来确定根节点和左右子树的边界。

先说为什么要用中序序列。中序遍历的顺序是“左子树、根、右子树”，只要知道根节点是谁，在中序序列里找到根的位置，根左边全是左子树的节点，根右边全是右子树的节点。而前序或后序遍历的作用是快速定位根节点：前序遍历的第一个节点是根，后序遍历的最后一个节点是根。所以两类题目本质都是“用一种遍历找根，用中序区分左右”。

以106为例，后序序列的最后一个元素就是根节点。在中序序列中找到这个根的位置index后，中序的左半段是左子树的中序序列，右半段是右子树的中序序列。接着需要计算出左子树的节点数量leftSize，再回到后序序列中，把后序序列也切成左子树后序和右子树后序两段，然后递归构造。难点在于后序序列的左右边界计算，因为后序序列中根节点在最末尾，去掉根之后剩下的前半段属于左子树、后半段属于右子树，这个分割比例必须根据左子树节点数量来确定。

105的推导逻辑完全对称，前序序列第一个是根，剩余的第二段到某个位置是左子树前序，再往后是右子树前序，同样用中序index分割左右。

这两题实操时强烈建议用HashMap把中序序列中的每个值和下标存下来，后面递归时直接O(1)查找根节点位置，否则每次都去线性扫描中序序列，整体复杂度会退化到O(n^2)。另外，区间下标建议统一用“左闭右开”，既能避免常见的差一错误，也方便和语言内置的切片操作对齐。

3. 实操过程与核心环节实现

3.1 关键代码：513与112/113

513的BFS写法：

public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int result = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (i == 0) { result = node.val; } if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } } return result; }

这段代码的关键是在每一层内检查当前节点是不是第一个出队的节点，是的话记录它的值。因为队列入队顺序固定是先左后右，所以每层第一个出队的节点一定是该层最左节点。

513的DFS写法：

int maxDepth = -1; int result = 0; public int findBottomLeftValue(TreeNode root) { dfs(root, 0); return result; } private void dfs(TreeNode node, int depth) { if (node == null) return; if (depth > maxDepth) { maxDepth = depth; result = node.val; } dfs(node.left, depth + 1); dfs(node.right, depth + 1); }

这里更新条件必须写成depth > maxDepth。因为先走左子树，同一层第一次到达的节点必然是该层最左节点。假如写成depth >= maxDepth，那么当遍历完左子树再遍历右子树时，右子树同层节点也会触发更新，最终覆盖掉最左值。

112路径总和的递归写法：

public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; targetSum -= root.val; if (root.left == null && root.right == null) { return targetSum == 0; } return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum); }

注意边界处理：root为null直接返回false，不能把空节点当成路径终点。叶子节点判断必须在递归内部完成，因为“路径的终点必须是叶子节点”这个条件不能由空节点判断来替代。

113路径总和 II的完整回溯写法：

List<List<Integer>> res = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> pathSum(TreeNode root, int targetSum) { dfs(root, targetSum); return res; } private void dfs(TreeNode node, int remain) { if (node == null) return; remain -= node.val; path.addLast(node.val); if (node.left == null && node.right == null && remain == 0) { res.add(new ArrayList<>(path)); } dfs(node.left, remain); dfs(node.right, remain); path.removeLast(); }

path使用LinkedList的removeLast可以高效地删除末尾元素。每次递归返回之前必须removeLast，这正是回溯中“撤销选择”的核心动作。把path加入结果集时一定要new一个ArrayList，否则res里存的都是同一个对象的引用，后续全会被改掉。

3.2 关键代码：106与105的重建核心

106从中序与后序遍历构造二叉树的实现：

Map<Integer, Integer> indexMap = new HashMap<>(); public TreeNode buildTree(int[] inorder, int[] postorder) { for (int i = 0; i < inorder.length; i++) { indexMap.put(inorder[i], i); } return build(inorder, 0, inorder.length, postorder, 0, postorder.length); } private TreeNode build(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) { if (inLeft >= inRight || postLeft >= postRight) return null; int rootVal = postorder[postRight - 1]; TreeNode root = new TreeNode(rootVal); int rootIndex = indexMap.get(rootVal); int leftSize = rootIndex - inLeft; root.left = build(inorder, inLeft, rootIndex, postorder, postLeft, postLeft + leftSize); root.right = build(inorder, rootIndex + 1, inRight, postorder, postLeft + leftSize, postRight - 1); return root; }

这里用左闭右开区间。rootIndex是根节点在中序序列中的位置，leftSize表示左子树的节点数量。后序序列中，左子树的后序段从postLeft开始，长度为leftSize；右子树的后序段紧跟着左子树，剩下到postRight - 1的位置，因为postRight - 1的位置是根节点，要排除掉。

105从前序与中序遍历构造二叉树的实现：

Map<Integer, Integer> indexMap = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for (int i = 0; i < inorder.length; i++) { indexMap.put(inorder[i], i); } return build(preorder, 0, preorder.length, inorder, 0, inorder.length); } private TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) { if (preLeft >= preRight || inLeft >= inRight) return null; int rootVal = preorder[preLeft]; TreeNode root = new TreeNode(rootVal); int rootIndex = indexMap.get(rootVal); int leftSize = rootIndex - inLeft; root.left = build(preorder, preLeft + 1, preLeft + 1 + leftSize, inorder, inLeft, rootIndex); root.right = build(preorder, preLeft + 1 + leftSize, preRight, inorder, rootIndex + 1, inRight); return root; }

前序序列第一个元素是根，所以左子树前序从preLeft + 1开始，长度是leftSize；右子树前序接着左子树结束的位置，一直到preRight。中序序列的切分与106一致。

两道题的差异只在根节点的来源不同，一个是取后序末尾，一个是取前序开头。很多朋友把这两道题分开记忆，其实完全没必要，只要抓住“中序负责切分左右，前序/后序负责定位根”这个规律，两道题可以一起记住。

3.3 手写一次递归推导，看调用栈怎么走

刷题光看代码有时候会晕，尤其是106这种区间切分的题。我拿一个简单例子走了一遍调用栈。

假设中序序列是[9, 3, 15, 20, 7]，后序序列是[9, 15, 7, 20, 3]。

第一次调用build时，postRight为5，根节点是postorder[4]=3。在中序里找到3的下标是1，于是leftSize=1-0=1。左子树的中序区间是[0,1)，对应后序区间是[0,0+1)，即postorder里只有[9]；右子树的中序区间是[2,5)，对应后序区间是[1,4)，即postorder里[15,7,20]。递归进去时，右子树区间[1,4)取末尾postorder[3]=20作为根，再在中序里找到20的下标是3，leftSize=3-2=1，又切分出左右子树，整个过程就是不断重复“取末尾根、中序定位、按leftSize切区间”的三部曲。

把每一步的区间值写在纸上，你会发现边界其实非常好推理，关键是第一次确定leftSize后，后序区间的右边界始终是postLeft + leftSize，这个公式一旦想明白就不会再出错。

4. 常见问题与排查技巧实录

4.1 五个反复踩的坑

第一个坑是513 DFS更新条件写松。用>=代替>，导致同一层后遍历的右子树节点覆盖掉左子树答案。排查方法很简单，在更新条件处打日志，打印每次访问的节点值和当前深度，立刻能看出哪个节点触发了错误更新。

第二个坑是112对空节点判断过于乐观。把root == null当成路径和为0来处理，结果根节点为空时直接返回true。实际题目里空树不应有合法路径，必须返回false；并且叶子判断必须显式检查左右子节点是否都为空，不能靠节点空来判断。

第三个坑是113回溯忘记恢复现场。路径收集正确、结果集却出现重复或残缺路径，十有八九是递归返回之前没有removeLast。这个坑最隐蔽的一点是，它不一定导致运行报错，只会让结果很怪，很多人因此排查半天。

第四个坑是106/105递归区间算错。常见的是把后序或前序的左右子树起点终点搞反。我建议把四个区间参数统一命名成inLeft、inRight、postLeft、postRight，每次递归前先在注释里标出当前区间到底代表哪棵子树，写清楚后再填参数。

第五个坑是HashMap建表后忘记考虑“值重复”。题目明确说的是“节点值互不相同”，但如果自己造测试用例时让二叉树存在重复值，HashMap会覆盖旧值导致index定位错误。刷题按题目约束走即可，但自己扩展场景时要明白这个前提。

4.2 面试答题的技巧：先讲思路再写码

这几道题面试出现频率很高，我刷完最大的心得是：面试官不是只看你写没写出代码，更想听你怎么拆解递归。

我一般按“递归三部曲”来讲：先明确参数和返回值，再说终止条件，最后讲单层逻辑。以106题为例，我会说参数是四个区间的起点终点，返回值是当前子树根节点；终止条件是区间为空；单层逻辑是取后序末尾的元素建根、在中序里定位、计算左子树长度、递归构建左右子树。这样讲，即使代码还没写，面试官已经知道你对题目有完整理解。

还有一个小技巧：遇到递归题，先在白板上画一棵三层小树，标出前序、中序、后序的访问顺序，再拿这个例子去套你的递归函数。画完图后，很多所谓的“边界问题”其实都变成了肉眼可见的区间范围问题。

4.3 关于复杂度的几句实话

这几道题的时间复杂度都好分析：513和112、113都是每个节点访问一次，时间复杂度O(n)，空间复杂度取决于树的形状，最坏退化到O(n)。106和105因为用了HashMap做中序索引，每次递归定位根节点都是O(1)，整体时间复杂度O(n)；如果不用HashMap，每次都要遍历中序序列找根，最坏会到O(n^2)。所以构造二叉树题，建索引表几乎是必做优化。

空间复杂度上，递归栈的深度与树高相关，对于普通的二叉树，面试时答O(h)即可，其中h为树高。如果树严重不平衡，递归栈深度会趋近于节点总数，那时候要小心栈溢出。真正生产环境遇到海量数据，我会优先翻译成迭代写法或者改用显式栈模拟。

5. 写在最后：我对递归题型的理解

今天这五道题刷下来，我最大的收获不是某道题的代码，而是想明白了一个通用规律：几乎所有二叉树递归题都可以拆成“当前节点要做什么”加“子树之间如何联系”两个问题。

513要的是在递归中维护“最深层最左”，112要的是把目标值沿路径传递，113在112基础上增加了路径的收集和撤销，106和105则是在区间切分中建树。如果你能对每道题都说出“当前节点负责干什么”“返回给上一层什么信息”“进入子树前要维护什么状态”，那这类题基本就通关了。

最后再分享一个小建议：刷递归题时不要只盯着通过率，一定要在纸上把递归调用栈画一遍。哪怕只画三层树，你就能看清递归终止条件为什么写在最前面，回溯的恢复语句为什么放在递归调用之后，区间参数为什么是这些数字。画过一次之后，你对递归的理解会比刷十道题还牢固。