刷二叉树最怕的不是不会递归而是每道题看讲解都懂放下教程自己写又卡壳。这一期训练营的五道题——513 找树左下角的值、112 路径总和、113 路径总和 II、106 从中序与后序遍历序列构造二叉树、105 从前序与中序遍历序列构造二叉树——表面看是五个独立题目拆开看其实是三个递进主题遍历变体里的深度优先、路径求和里的回溯、以及利用遍历序列还原二叉树的分治。今天把这组题做完后的完整思考写下来适合刚入门递归、想系统刷二叉树的人参考。这个组合的价值在于它不逼你背代码而是逼你把二叉树题的分类逻辑搞清楚。前两题练的是递归过程中如何携带和维护状态中间两题练的是回溯与结果收集最后两题练的是分治边界推导。五道题环环相扣难度曲线也很合理——从遍历到搜索再到构造一套下来很多常见的二叉树题套路就都串起来了。1. 这五道题放在一起练的底层逻辑1.1 一个训练单元里的三个递进主题很多人把二叉树题按“前序、中序、后序、层序”划分这当然没错但刷到后面你会发现真正决定代码形态的是“递归函数到底要返回什么”以及“进入下一层递归前要做什么”。513 属于“遍历变体”本质还是深度优先遍历只是多带了一个深度参数用来锁定最后一层的最左节点。它练的是在递归过程中更新全局记录的能力。112 和 113 属于“路径搜索”核心不是遍历顺序而是递归到叶子时能否判断路径是否满足条件以及如何把一条条路径完整保留下来。105 和 106 则彻底换了套路不再关心路径而是利用中序序列的左右划分来还原整棵二叉树练的是区间切分和分治边界推导。所以这五道题不是简单地“今天多做了几题”而是一个完整的能力闭环会遍历才能理解和维护递归过程中的中间状态会回溯才能从“找一条路径”扩展到“找所有路径”会分治才能从“读一棵树”升级到“建一棵树”。1.2 递归函数返回值设计的判断标准这五道题里有个很容易被忽略但特别关键的决策点递归函数到底应不应该有返回值。我的判断标准很简单如果递归只需要找一个答案确定了就不用继续找那就返回布尔值或节点引用让它短路如果递归要收集所有可能结果那就别返回用 void 外部结果集配合回溯去收集。112 显然属于前者113 属于后者105 和 106 属于构造型递归每次要返回新建的节点让上一层接住。很多同学写 113 的时候会不自觉地想把“路径列表”作为返回值一路传上来结果写成一团乱麻。根源就是没在动手前想清楚你要的是单一答案还是全部答案。全部答案就必须借助外部容器把所有结果暂存起来否则路径会在回溯时被撤销。2. 513 找树左下角的值先序遍历里的“深度感知”2.1 题目真正问的是什么先说一个容易被题目带偏的地方“树左下角的值”不是整棵树最左边的节点而是最后一层的最左节点。比如一棵树只有左子树特别深那么右下角反而是“左下角”。所以这题的关键不是往左走而是确定“深度”和“最左”两个维度的优先级先保证是最大深度再保证是同深度里最靠左。理解了这一点解题思路就清晰了深度优先遍历时同一层第一次被访问到的节点就是该层最左节点而我们只需要记录“深度第一次超过当前最大深度”的那个节点。因为前序遍历天然是“先左后右”所以第一个到达某个新深度的节点一定就是这一层最左的节点。2.2 递归解法用最大深度锁定第一个叶子递归写法的核心是设置两个全局变量max_depth记录当前遍历到的最大深度result记录该最大深度下第一次出现的叶子值。每次遇到叶子节点判断它的深度是否大于max_depth如果是就更新结果。因为访问顺序是先左后右同一深度下左边的节点一定先被访问所以这个值就是左下角。class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) - int: self.max_depth -1 self.result root.val def dfs(node, depth): # 只有叶子节点才参与更新 if not node.left and not node.right: if depth self.max_depth: self.max_depth depth self.result node.val return if node.left: dfs(node.left, depth 1) if node.right: dfs(node.right, depth 1) dfs(root, 0) return self.result为什么只在叶子节点更新因为最后一层的最左节点必然是叶子节点。它不是叶子就说明下面还有一层它就不可能属于“最后一层”。所以看到叶子才做深度比较逻辑上更严谨也不会有遗漏。我实际写的过程中踩过一个小坑max_depth初始值不要设成 0。如果根节点就是唯一节点且初始值是 0那么叶子深度 0 不大于 0结果不会更新就会兜底返回root.val表面看没问题但一旦后续逻辑改复杂很容易埋隐患。初始化为 -1 更安全保证第一个叶子必定能触发更新。2.3 迭代解法反层序遍历的一种取巧写法这题用层序也能做而且有个特别取巧的版本正常的层序是从左往右入队出队顺序就是从左到右。如果我们入队时先放右孩子再放左孩子出队顺序就变成了从右到左。这样每层遍历完最后出队的节点就正好落在“最左下角”。from collections import deque class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) - int: q deque([root]) ans root.val while q: node q.popleft() ans node.val if node.right: q.append(node.right) if node.left: q.append(node.left) return ans代码很短但要理解它为什么成立反层序出队顺序中下一层的节点会排到当前层右侧节点之后一层一层剥下去最后一个出队的就是最底层的“最右”不这里是反层序所以最后一个出队的是“最左”。我这么解释可能绕建议自己拿个例子画一下1 / \ 2 3 / / \ 4 6 5反层序出队顺序是1 → 3 → 2 → 5 → 6 → 4最后一个是 4正好是左下角。这个技巧在面试里说出来会很加分因为对方能看出你不只会递归还懂层序的变形。3. 112 与 113路径总和从“有没有”到“所有”3.1 112 路径总和递归的布尔返回与短路优化112 的经典写法是把targetSum改为“剩余值”每次往下走都减去当前节点值。到叶子节点时如果剩余值正好等于当前节点值说明路径成立。class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) - bool: if not root: return False if not root.left and not root.right: return root.val targetSum return self.hasPathSum(root.left, targetSum - root.val) or \ self.hasPathSum(root.right, targetSum - root.val)这里有个很重要的设计当左子树递归返回True时or后面的右子树递归根本不会执行这就是短路优化。递归里一旦出现这种“只找一个答案”的形态就可以放心用返回值做短路不用额外维护全局标志位。当然你也可以写全局标记但明显不如这种写法干净。很多人写这题时会纠结要不要处理root为空的情况。实际上你只需要在递归入口判断一次空树内部递归时虽然当前节点可能为空但递归调用前已经被父节点的left/right判断挡掉了吗并没有比如一棵树只有一个左孩子递归到root.right时就是空节点。所以递归函数内部必须处理node None的情况。我在上面的写法里虽然显式处理了root为空但递归子问题时并没有额外判空因为targetSum - root.val之后如果子节点为 None下一层入口的not root就会兜住。这个逻辑是自洽的。3.2 113 路径总和 II回溯模板的正确打开方式一旦要求“找所有路径”代码就变了。核心区别在于递归过程中收集的路径需要被保留而递归返回后路径需要恢复到之前的状态。这就是回溯。class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]: res [] path [] def dfs(node, rest): if not node: return path.append(node.val) if not node.left and not node.right: if rest node.val: res.append(path[:]) # 深拷贝当前路径 else: dfs(node.left, rest - node.val) dfs(node.right, rest - node.val) path.pop() # 回溯撤销当前节点 dfs(root, targetSum) return res两个重点必须划出来第一res.append(path)是错的。Python 里列表是引用类型path在后续回溯中会被pop修改你存进res的那个引用也会跟着变。必须用path[:]或list(path)拷贝一份。第二path.pop()必须放在递归返回之后。仔细看结构先 append 当前节点然后递归处理左右子树等左右子树全部处理完回到当前层再pop撤销自己。如果提前 pop路径就断了后面的结果收集会全部错乱。很多模板把dfs(node.left)和dfs(node.right)写在一起再用if区分叶子分支。我更推荐上面这种“先处理叶子再递归非叶子”的结构因为逻辑上直接对应“叶子是终点”的语义不容易漏掉叶子。3.3 路径类题目一个通用套路做完 112 和 113可以顺手总结一套路径类题目的通用套路用rest或remain表示“还差多少”递归时用当前节点值更新判断“到达叶子”作为终止条件叶子判断not node.left and not node.right收集所有路径时必须深拷贝递归返回前必须撤销本层的修改。这套模板不仅适用于二叉树路径求和也适用于网格 DFS、回溯排列组合等很多场景。path.pop()的位置永远和path.append(node.val)对应形式上像一对括号先 append经过一整轮递归后再 pop。这个“括号感”很重要可以用它来自查回溯代码是否正确。4. 105 与 106用中序切分用前序/后序定根4.1 为什么构造二叉树必须有中序序列先解决一个认知问题为什么“前序 后序”不能唯一确定二叉树前序[1, 2]和后序[2, 1]可以对应“1 的左孩子是 2”也可以对应“1 的右孩子是 2”两者前序和后序完全一样。原因在于前序和后序都只能告诉我们“根在哪头”却无法区分左右子树的分界。而中序序列提供了关键信息根节点左边的值都在左子树右边的值都在右子树。有了这个左右划分前序或后序里的节点才能被精确地放进对应的子树里。所以在 LC 105 和 106 里中序序列是不可或缺的“参照系”前序或后序负责提供根节点。4.2 106 从中序后序构造六步切割法后序遍历顺序是“左 → 右 → 根”所以后序数组的最后一个元素就是整棵树的根。拿到根之后去中序数组中找到根的位置中序左边是左子树右边是右子树。得到左右子树各自的长度后再回到后序数组按长度切出左子树后序和右子树后序递归构造。class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) - Optional[TreeNode]: if not inorder: return None root_val postorder[-1] root TreeNode(root_val) idx inorder.index(root_val) left_in inorder[:idx] right_in inorder[idx 1:] left_post postorder[:len(left_in)] right_post postorder[len(left_in):-1] root.left self.buildTree(left_in, left_post) root.right self.buildTree(right_in, right_post) return root这段代码的六个步骤非常机械后序最后一个节点是根在中序中找到根的位置中序根左边是左子树中序右边是右子树中序用左子树中序长度确定左子树后序即后序从头开始的那一段剩余部分去掉最后一个根节点就是右子树后序递归构建左右子树。我用一组数据验证一下。中序[9, 3, 15, 20, 7]后序[9, 15, 7, 20, 3]根是 3中序中 3 在索引 1左子树中序[9]右子树中序[15, 20, 7]左子树后序是后序前 1 个[9]右子树后序是[15, 7, 20]递归右子树时后序[15, 7, 20]的根是 20中序里 20 左侧是[15]右侧是[7]于是 20 的左孩子是 15右孩子是 7。最终结构就是3 / \ 9 20 / \ 15 7每次递归都会吃掉一小段中序和小段后序当inorder为空就返回 None边界很干净。4.3 105 从前序中序构造换汤不换药的切割前序遍历顺序是“根 → 左 → 右”所以前序的第一个元素是根。切分逻辑和中序后序完全对称class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) - Optional[TreeNode]: if not inorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) left_in inorder[:idx] right_in inorder[idx 1:] left_pre preorder[1:1 len(left_in)] right_pre preorder[1 len(left_in):] root.left self.buildTree(left_pre, left_in) root.right self.buildTree(right_pre, right_in) return root唯一的不同在于中序 后序后序的根在末尾左子树后序从开头取前序 中序前序的根在开头左子树前序从索引 1 开始取。两个版本建议放在一起对比记忆而不是分开刷。你会发现核心只有一条中序决定左右边界前序/后序决定根的位置。这里我想特别提醒一个容易写错的细节切前序左子树时切片终点是1 len(left_in)起点是 1因为前序第一个元素已经被根占掉了。而切后序右子树时终点是-1因为后序最后一个元素是根要把它排除。很多人第一次写会把终点写成len(left_post)之类的实际上是左子树长度而不是右子树长度一坨乱。4.4 切片版与索引版代码简洁和性能的取舍上面给的版本是“切片版”好处是逻辑直观、适合初学坏处是每次递归都创建新数组空间复杂度偏高。LeetCode 数据量小切片版完全能过但面试时如果被追问最好能写出“索引版”。索引版的思路是不切片只用(in_lo, in_hi)和(post_lo, post_hi)四个索引锁定当前子树在原始数组里的范围。以 106 为例class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) - Optional[TreeNode]: self.post_idx len(postorder) - 1 self.in_pos {v: i for i, v in enumerate(inorder)} def build(in_lo, in_hi): if in_lo in_hi: return None root_val postorder[self.post_idx] root TreeNode(root_val) self.post_idx - 1 idx self.in_pos[root_val] root.right build(idx 1, in_hi) root.left build(in_lo, idx - 1) return root return build(0, len(inorder) - 1)注意这里必须先构建右子树再构建左子树。因为后序遍历是“左 → 右 → 根”倒着处理时根之后先遇到的是右子树根。如果先建左子树索引就会乱套。这个细节是索引版最容易出错的地方。同理前序 中序的索引版要先建左子树再建右子树因为前序正着遍历时根之后就是左子树。这个对称关系很有用论文本里可以写出来面试时也容易给对方留下好印象。5. 常见问题与排查技巧实录5.1 这几道题最容易踩的五个坑我实际刷完这组题把容易出错的地方整理成一个速查表。题目典型错误正确思路513以为“左下角”就是一直往左走是最后一层的最左节点递归要带深度判断513迭代版忘记先入右孩子再入左孩子反层序最后出队的才是左下角入队顺序是右在前左在后112空节点被当成路径终点只有叶子节点才算终点空节点直接返回 False113res.append(path)结果全是空列表用path[:]深拷贝路径防止后续 pop 污染113path.pop()放在递归之前pop 必须在递归返回之后与 append 成对出现106/105后序切右子树时忘记排除根节点右子树后序终点的-1不能省前序左子树切片起点是 1106/105中序找不到根导致越界题目保证节点值不重复用哈希表把值映射到索引最稳还有一个很隐蔽的坑出现在 105 和 106 上中序数组元素值不重复的前提一旦不成立index()就会取到错误位置。LeetCode 默认节点值唯一但实际项目里这种情况并不常见。为了保险索引版里用哈希表可以在创建时顺便检查重复值。5.2 二叉树相关题目的调试手段构造二叉树这种题目代码写完了千万别急着交。我习惯用一个“可视化断言”的方法自检把构造出的树再跑一次前序/中序/后序遍历看输出的序列是否和题目输入一致。如果能写个快速函数把树打印成缩进结构排查效率会高很多。def print_tree(root, level0, prefixroot): if root is not None: print( * (level * 4) f{prefix}: {root.val}) print_tree(root.left, level 1, left) print_tree(root.right, level 1, right)一个小技巧是在递归函数里打印当前处理的子树范围。比如索引版构造 106 时在每个递归入口打印(in_lo, in_hi)和post_idx一眼就能看出索引有没有错位。这种“打印递归区间”的调试方式比单步断点更快特别适合递归题。另外如果某道题提交后超时先怀疑两件事一是递归里重复做了大量哈希查找比如每次都index()这种在长度上万时就会退化二是递归是否出现了无限循环通常是切分边界写错导致子树区间没有缩小。6. 一点刷题之外的心得刷完这一组题我个人最强烈的感受是二叉树的递归题看起来花样多本质上就几个套路——维护路径、维护深度、按区间分治。513 和 112 让我体会到“递归函数的返回值设计”113 让我意识到“回溯和递归是一体两面”105 和 106 则逼着我把“区间开闭”这个基本功练扎实。如果你也刚刷到这些题我建议不要只满足于把代码跑通试试这几件事第一把 513 的递归版和迭代版都写一遍对比两者的状态维护方式第二把 113 的模板背下来再用同一个模板去做二叉树的所有路径这类题第三105 和 106 先写切片版理解了之后立刻改写索引版改完再对比两个版本的处理差异。这样练完比单纯刷过五题要扎实得多。 
长河君 · 2026/10/13 19:39:31 · 阅读 1.2k 二叉树递归刷题总结：深度优先、回溯与分治构造的完整套路
刷二叉树最怕的不是不会递归而是每道题看讲解都懂放下教程自己写又卡壳。这一期训练营的五道题——513 找树左下角的值、112 路径总和、113 路径总和 II、106 从中序与后序遍历序列构造二叉树、105 从前序与中序遍历序列构造二叉树——表面看是五个独立题目拆开看其实是三个递进主题遍历变体里的深度优先、路径求和里的回溯、以及利用遍历序列还原二叉树的分治。今天把这组题做完后的完整思考写下来适合刚入门递归、想系统刷二叉树的人参考。这个组合的价值在于它不逼你背代码而是逼你把二叉树题的分类逻辑搞清楚。前两题练的是递归过程中如何携带和维护状态中间两题练的是回溯与结果收集最后两题练的是分治边界推导。五道题环环相扣难度曲线也很合理——从遍历到搜索再到构造一套下来很多常见的二叉树题套路就都串起来了。1. 这五道题放在一起练的底层逻辑1.1 一个训练单元里的三个递进主题很多人把二叉树题按“前序、中序、后序、层序”划分这当然没错但刷到后面你会发现真正决定代码形态的是“递归函数到底要返回什么”以及“进入下一层递归前要做什么”。513 属于“遍历变体”本质还是深度优先遍历只是多带了一个深度参数用来锁定最后一层的最左节点。它练的是在递归过程中更新全局记录的能力。112 和 113 属于“路径搜索”核心不是遍历顺序而是递归到叶子时能否判断路径是否满足条件以及如何把一条条路径完整保留下来。105 和 106 则彻底换了套路不再关心路径而是利用中序序列的左右划分来还原整棵二叉树练的是区间切分和分治边界推导。所以这五道题不是简单地“今天多做了几题”而是一个完整的能力闭环会遍历才能理解和维护递归过程中的中间状态会回溯才能从“找一条路径”扩展到“找所有路径”会分治才能从“读一棵树”升级到“建一棵树”。1.2 递归函数返回值设计的判断标准这五道题里有个很容易被忽略但特别关键的决策点递归函数到底应不应该有返回值。我的判断标准很简单如果递归只需要找一个答案确定了就不用继续找那就返回布尔值或节点引用让它短路如果递归要收集所有可能结果那就别返回用 void 外部结果集配合回溯去收集。112 显然属于前者113 属于后者105 和 106 属于构造型递归每次要返回新建的节点让上一层接住。很多同学写 113 的时候会不自觉地想把“路径列表”作为返回值一路传上来结果写成一团乱麻。根源就是没在动手前想清楚你要的是单一答案还是全部答案。全部答案就必须借助外部容器把所有结果暂存起来否则路径会在回溯时被撤销。2. 513 找树左下角的值先序遍历里的“深度感知”2.1 题目真正问的是什么先说一个容易被题目带偏的地方“树左下角的值”不是整棵树最左边的节点而是最后一层的最左节点。比如一棵树只有左子树特别深那么右下角反而是“左下角”。所以这题的关键不是往左走而是确定“深度”和“最左”两个维度的优先级先保证是最大深度再保证是同深度里最靠左。理解了这一点解题思路就清晰了深度优先遍历时同一层第一次被访问到的节点就是该层最左节点而我们只需要记录“深度第一次超过当前最大深度”的那个节点。因为前序遍历天然是“先左后右”所以第一个到达某个新深度的节点一定就是这一层最左的节点。2.2 递归解法用最大深度锁定第一个叶子递归写法的核心是设置两个全局变量max_depth记录当前遍历到的最大深度result记录该最大深度下第一次出现的叶子值。每次遇到叶子节点判断它的深度是否大于max_depth如果是就更新结果。因为访问顺序是先左后右同一深度下左边的节点一定先被访问所以这个值就是左下角。class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) - int: self.max_depth -1 self.result root.val def dfs(node, depth): # 只有叶子节点才参与更新 if not node.left and not node.right: if depth self.max_depth: self.max_depth depth self.result node.val return if node.left: dfs(node.left, depth 1) if node.right: dfs(node.right, depth 1) dfs(root, 0) return self.result为什么只在叶子节点更新因为最后一层的最左节点必然是叶子节点。它不是叶子就说明下面还有一层它就不可能属于“最后一层”。所以看到叶子才做深度比较逻辑上更严谨也不会有遗漏。我实际写的过程中踩过一个小坑max_depth初始值不要设成 0。如果根节点就是唯一节点且初始值是 0那么叶子深度 0 不大于 0结果不会更新就会兜底返回root.val表面看没问题但一旦后续逻辑改复杂很容易埋隐患。初始化为 -1 更安全保证第一个叶子必定能触发更新。2.3 迭代解法反层序遍历的一种取巧写法这题用层序也能做而且有个特别取巧的版本正常的层序是从左往右入队出队顺序就是从左到右。如果我们入队时先放右孩子再放左孩子出队顺序就变成了从右到左。这样每层遍历完最后出队的节点就正好落在“最左下角”。from collections import deque class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) - int: q deque([root]) ans root.val while q: node q.popleft() ans node.val if node.right: q.append(node.right) if node.left: q.append(node.left) return ans代码很短但要理解它为什么成立反层序出队顺序中下一层的节点会排到当前层右侧节点之后一层一层剥下去最后一个出队的就是最底层的“最右”不这里是反层序所以最后一个出队的是“最左”。我这么解释可能绕建议自己拿个例子画一下1 / \ 2 3 / / \ 4 6 5反层序出队顺序是1 → 3 → 2 → 5 → 6 → 4最后一个是 4正好是左下角。这个技巧在面试里说出来会很加分因为对方能看出你不只会递归还懂层序的变形。3. 112 与 113路径总和从“有没有”到“所有”3.1 112 路径总和递归的布尔返回与短路优化112 的经典写法是把targetSum改为“剩余值”每次往下走都减去当前节点值。到叶子节点时如果剩余值正好等于当前节点值说明路径成立。class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) - bool: if not root: return False if not root.left and not root.right: return root.val targetSum return self.hasPathSum(root.left, targetSum - root.val) or \ self.hasPathSum(root.right, targetSum - root.val)这里有个很重要的设计当左子树递归返回True时or后面的右子树递归根本不会执行这就是短路优化。递归里一旦出现这种“只找一个答案”的形态就可以放心用返回值做短路不用额外维护全局标志位。当然你也可以写全局标记但明显不如这种写法干净。很多人写这题时会纠结要不要处理root为空的情况。实际上你只需要在递归入口判断一次空树内部递归时虽然当前节点可能为空但递归调用前已经被父节点的left/right判断挡掉了吗并没有比如一棵树只有一个左孩子递归到root.right时就是空节点。所以递归函数内部必须处理node None的情况。我在上面的写法里虽然显式处理了root为空但递归子问题时并没有额外判空因为targetSum - root.val之后如果子节点为 None下一层入口的not root就会兜住。这个逻辑是自洽的。3.2 113 路径总和 II回溯模板的正确打开方式一旦要求“找所有路径”代码就变了。核心区别在于递归过程中收集的路径需要被保留而递归返回后路径需要恢复到之前的状态。这就是回溯。class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]: res [] path [] def dfs(node, rest): if not node: return path.append(node.val) if not node.left and not node.right: if rest node.val: res.append(path[:]) # 深拷贝当前路径 else: dfs(node.left, rest - node.val) dfs(node.right, rest - node.val) path.pop() # 回溯撤销当前节点 dfs(root, targetSum) return res两个重点必须划出来第一res.append(path)是错的。Python 里列表是引用类型path在后续回溯中会被pop修改你存进res的那个引用也会跟着变。必须用path[:]或list(path)拷贝一份。第二path.pop()必须放在递归返回之后。仔细看结构先 append 当前节点然后递归处理左右子树等左右子树全部处理完回到当前层再pop撤销自己。如果提前 pop路径就断了后面的结果收集会全部错乱。很多模板把dfs(node.left)和dfs(node.right)写在一起再用if区分叶子分支。我更推荐上面这种“先处理叶子再递归非叶子”的结构因为逻辑上直接对应“叶子是终点”的语义不容易漏掉叶子。3.3 路径类题目一个通用套路做完 112 和 113可以顺手总结一套路径类题目的通用套路用rest或remain表示“还差多少”递归时用当前节点值更新判断“到达叶子”作为终止条件叶子判断not node.left and not node.right收集所有路径时必须深拷贝递归返回前必须撤销本层的修改。这套模板不仅适用于二叉树路径求和也适用于网格 DFS、回溯排列组合等很多场景。path.pop()的位置永远和path.append(node.val)对应形式上像一对括号先 append经过一整轮递归后再 pop。这个“括号感”很重要可以用它来自查回溯代码是否正确。4. 105 与 106用中序切分用前序/后序定根4.1 为什么构造二叉树必须有中序序列先解决一个认知问题为什么“前序 后序”不能唯一确定二叉树前序[1, 2]和后序[2, 1]可以对应“1 的左孩子是 2”也可以对应“1 的右孩子是 2”两者前序和后序完全一样。原因在于前序和后序都只能告诉我们“根在哪头”却无法区分左右子树的分界。而中序序列提供了关键信息根节点左边的值都在左子树右边的值都在右子树。有了这个左右划分前序或后序里的节点才能被精确地放进对应的子树里。所以在 LC 105 和 106 里中序序列是不可或缺的“参照系”前序或后序负责提供根节点。4.2 106 从中序后序构造六步切割法后序遍历顺序是“左 → 右 → 根”所以后序数组的最后一个元素就是整棵树的根。拿到根之后去中序数组中找到根的位置中序左边是左子树右边是右子树。得到左右子树各自的长度后再回到后序数组按长度切出左子树后序和右子树后序递归构造。class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) - Optional[TreeNode]: if not inorder: return None root_val postorder[-1] root TreeNode(root_val) idx inorder.index(root_val) left_in inorder[:idx] right_in inorder[idx 1:] left_post postorder[:len(left_in)] right_post postorder[len(left_in):-1] root.left self.buildTree(left_in, left_post) root.right self.buildTree(right_in, right_post) return root这段代码的六个步骤非常机械后序最后一个节点是根在中序中找到根的位置中序根左边是左子树中序右边是右子树中序用左子树中序长度确定左子树后序即后序从头开始的那一段剩余部分去掉最后一个根节点就是右子树后序递归构建左右子树。我用一组数据验证一下。中序[9, 3, 15, 20, 7]后序[9, 15, 7, 20, 3]根是 3中序中 3 在索引 1左子树中序[9]右子树中序[15, 20, 7]左子树后序是后序前 1 个[9]右子树后序是[15, 7, 20]递归右子树时后序[15, 7, 20]的根是 20中序里 20 左侧是[15]右侧是[7]于是 20 的左孩子是 15右孩子是 7。最终结构就是3 / \ 9 20 / \ 15 7每次递归都会吃掉一小段中序和小段后序当inorder为空就返回 None边界很干净。4.3 105 从前序中序构造换汤不换药的切割前序遍历顺序是“根 → 左 → 右”所以前序的第一个元素是根。切分逻辑和中序后序完全对称class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) - Optional[TreeNode]: if not inorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) left_in inorder[:idx] right_in inorder[idx 1:] left_pre preorder[1:1 len(left_in)] right_pre preorder[1 len(left_in):] root.left self.buildTree(left_pre, left_in) root.right self.buildTree(right_pre, right_in) return root唯一的不同在于中序 后序后序的根在末尾左子树后序从开头取前序 中序前序的根在开头左子树前序从索引 1 开始取。两个版本建议放在一起对比记忆而不是分开刷。你会发现核心只有一条中序决定左右边界前序/后序决定根的位置。这里我想特别提醒一个容易写错的细节切前序左子树时切片终点是1 len(left_in)起点是 1因为前序第一个元素已经被根占掉了。而切后序右子树时终点是-1因为后序最后一个元素是根要把它排除。很多人第一次写会把终点写成len(left_post)之类的实际上是左子树长度而不是右子树长度一坨乱。4.4 切片版与索引版代码简洁和性能的取舍上面给的版本是“切片版”好处是逻辑直观、适合初学坏处是每次递归都创建新数组空间复杂度偏高。LeetCode 数据量小切片版完全能过但面试时如果被追问最好能写出“索引版”。索引版的思路是不切片只用(in_lo, in_hi)和(post_lo, post_hi)四个索引锁定当前子树在原始数组里的范围。以 106 为例class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) - Optional[TreeNode]: self.post_idx len(postorder) - 1 self.in_pos {v: i for i, v in enumerate(inorder)} def build(in_lo, in_hi): if in_lo in_hi: return None root_val postorder[self.post_idx] root TreeNode(root_val) self.post_idx - 1 idx self.in_pos[root_val] root.right build(idx 1, in_hi) root.left build(in_lo, idx - 1) return root return build(0, len(inorder) - 1)注意这里必须先构建右子树再构建左子树。因为后序遍历是“左 → 右 → 根”倒着处理时根之后先遇到的是右子树根。如果先建左子树索引就会乱套。这个细节是索引版最容易出错的地方。同理前序 中序的索引版要先建左子树再建右子树因为前序正着遍历时根之后就是左子树。这个对称关系很有用论文本里可以写出来面试时也容易给对方留下好印象。5. 常见问题与排查技巧实录5.1 这几道题最容易踩的五个坑我实际刷完这组题把容易出错的地方整理成一个速查表。题目典型错误正确思路513以为“左下角”就是一直往左走是最后一层的最左节点递归要带深度判断513迭代版忘记先入右孩子再入左孩子反层序最后出队的才是左下角入队顺序是右在前左在后112空节点被当成路径终点只有叶子节点才算终点空节点直接返回 False113res.append(path)结果全是空列表用path[:]深拷贝路径防止后续 pop 污染113path.pop()放在递归之前pop 必须在递归返回之后与 append 成对出现106/105后序切右子树时忘记排除根节点右子树后序终点的-1不能省前序左子树切片起点是 1106/105中序找不到根导致越界题目保证节点值不重复用哈希表把值映射到索引最稳还有一个很隐蔽的坑出现在 105 和 106 上中序数组元素值不重复的前提一旦不成立index()就会取到错误位置。LeetCode 默认节点值唯一但实际项目里这种情况并不常见。为了保险索引版里用哈希表可以在创建时顺便检查重复值。5.2 二叉树相关题目的调试手段构造二叉树这种题目代码写完了千万别急着交。我习惯用一个“可视化断言”的方法自检把构造出的树再跑一次前序/中序/后序遍历看输出的序列是否和题目输入一致。如果能写个快速函数把树打印成缩进结构排查效率会高很多。def print_tree(root, level0, prefixroot): if root is not None: print( * (level * 4) f{prefix}: {root.val}) print_tree(root.left, level 1, left) print_tree(root.right, level 1, right)一个小技巧是在递归函数里打印当前处理的子树范围。比如索引版构造 106 时在每个递归入口打印(in_lo, in_hi)和post_idx一眼就能看出索引有没有错位。这种“打印递归区间”的调试方式比单步断点更快特别适合递归题。另外如果某道题提交后超时先怀疑两件事一是递归里重复做了大量哈希查找比如每次都index()这种在长度上万时就会退化二是递归是否出现了无限循环通常是切分边界写错导致子树区间没有缩小。6. 一点刷题之外的心得刷完这一组题我个人最强烈的感受是二叉树的递归题看起来花样多本质上就几个套路——维护路径、维护深度、按区间分治。513 和 112 让我体会到“递归函数的返回值设计”113 让我意识到“回溯和递归是一体两面”105 和 106 则逼着我把“区间开闭”这个基本功练扎实。如果你也刚刷到这些题我建议不要只满足于把代码跑通试试这几件事第一把 513 的递归版和迭代版都写一遍对比两者的状态维护方式第二把 113 的模板背下来再用同一个模板去做二叉树的所有路径这类题第三105 和 106 先写切片版理解了之后立刻改写索引版改完再对比两个版本的处理差异。这样练完比单纯刷过五题要扎实得多。