刷到这一天的题目时我第一反应是「二叉树章节终于从纯遍历进入到了应用层」。代码随想录前几天的内容都在讲前中后序、层序遍历怎么写而第十六天这三道题——513.找树左下角的值、112.路径总和、106.从中序与后序遍历序列构造二叉树——分别从「遍历结果的加工」「递归回溯的经典范式」「利用遍历序列反向重建二叉树」三个角度把之前学的遍历能力真正用了起来。很多人刷到这里会觉得题目变难了其实是因为这三题正好卡在「会写遍历」和「会用遍历」之间的坎上。这篇就按我实际刷下来的理解把三道题串起来讲讲顺便把我踩过的坑和调试思路一并交代清楚。1. 三道题放在同一天并不是偶然的1.1 从「遍历二叉树」到「利用遍历解决问题」的转折点如果你跟着代码随想录的节奏走会发现前面几天的核心就是反复练遍历递归三要素、迭代法模拟栈、统一迭代法、层序队列模板。到了第十六天题目不再满足于「把节点打印出来」而是要求你从遍历过程中提取出有特定意义的信息。513要找的是最后一层的最左节点112要判断是否存在一条满足路径和的根到叶子路径106则是给你两条遍历序列、让你把整棵树还原出来。这三件事本质上都在问一个问题你到底是真正理解了遍历的过程还是只会背模板我自己刷题有一个体会遍历模板背得再熟遇到这种变体题还是会露馅。因为变体题考的不是「会不会写三行代码」而是「遍历过程中每个节点被你经过时你有没有能力额外记录点什么」。513题就是典型的「额外记录」112题则是「在递归过程中把目标值逐层传递」106题最狠直接要求你倒过来推——给你遍历结果反推树结构。1.2 三道题对应的三项核心能力我习惯把这三道题对应到三个能力维度上这样复习时不容易乱。题目考察能力底层遍历方式核心难点513. 找树左下角的值遍历中的信息提取DFS或BFS如何保证记录的是「最后一层」且「最左」112. 路径总和递归回溯的最小闭环前中后序皆可终止条件的正确设置与回溯的隐藏写法106. 从中序与后序遍历构造二叉树分治思想与切分区间后序定根、中序分左右切割索引的准确性这三个能力维度——信息提取、递归回溯、分治切分——基本覆盖了二叉树题目里最常出现的套路。把这三题吃透后面遇到路径总和II、最大二叉树、合并二叉树这些题你会觉得眼熟很多。接下来说说每道题具体怎么解。2. 513.找树左下角的值别被「左下角」三个字带偏题目描述很简单给定一棵二叉树返回其「最后一行」的「最左边的值」。注意题目说的是树的最后一行不是左子树的最左下角。如果一棵树最后一行的最左边节点在右子树上那答案同样是这个右子树节点。很多人第一次看到题名就会想当然地往左子树钻这个思维惯性是第一道坎。2.1 递归解法DFS加深度标记先左后右是关键递归解法的思路非常直白用 DFS 遍历整棵树同时记录当前深度。每当到达一个叶子节点时如果当前深度比之前记录的最大深度还要大说明第一次到达了一个更深层那这个节点一定是这一层最左边的节点——前提是你必须先递归左孩子再递归右孩子。class Solution { public: int maxDepth -1; int result 0; void traversal(TreeNode* node, int depth) { if (node-left nullptr node-right nullptr) { if (depth maxDepth) { maxDepth depth; result node-val; } return; } if (node-left) traversal(node-left, depth 1); if (node-right) traversal(node-right, depth 1); } int findBottomLeftValue(TreeNode* root) { traversal(root, 0); return result; } };这里有两个细节值得展开。第一为什么只在叶子节点处判断因为「最后一行」的节点必然是叶子节点非叶子节点下面还有孩子不可能是最后一行的内容所以只在左右孩子都为空时检查深度逻辑上是完备的。第二为什么必须是depth maxDepth而不是如果是那么在同一深度下右边的叶子节点会把左边叶子节点的结果覆盖掉最后返回的就是该层最右侧节点跟题目要求正好相反。我刚开始写的时候就用错过一测用例就发现结果不对排查了半天才意识到是这个比较符号的问题。所以这个是保证「最左」的关键必须想明白为什么而不是死记。2.2 层序解法换个角度从右往左入队如果会层序遍历这道题其实还有一种更取巧的解法。一般的层序遍历是从左往右依次入队出队顺序也是从左往右。那我把入队顺序改成先右孩子再左孩子这样每一层出队的时候右边的节点会先被弹出。当整棵树遍历完之后队列里最后一个弹出的节点自然是最后一层最左边的节点。class Solution { public: int findBottomLeftValue(TreeNode* root) { queueTreeNode* q; q.push(root); TreeNode* node nullptr; while (!q.empty()) { node q.front(); q.pop(); if (node-right) q.push(node-right); if (node-left) q.push(node-left); } return node-val; } };这段代码连层数都不用记BFS 天然一层一层往下走出队顺序又是每层从右到左所以最后出队的节点一定是「最底层的最左节点」。我第一次看到这个解法时觉得挺妙的它把问题从「记录最大深度再找最左」转化成了「改变遍历顺序让答案自动落在最后」。这两种解法递归版适合用来深入理解 DFS 深度更新迭代版适合在面试时快速写出来各有各的价值。2.3 递归和迭代选哪个我的建议是优先掌握递归解法因为递归里「用深度值标记并选择性更新」这个模式在二叉树题目里复用率极高比如后面求二叉树深度、判断平衡二叉树都要用到。层序解法可以作为补充顺手写上也不费劲但如果依赖 BFS 模板遇到一些需要深度的变种题可能就不好使了。两道都写一遍对遍历的理解会更深一层。3. 112.路径总和递归回溯的最小闭环题目要求给定一棵二叉树和一个目标和 targetSum判断是否存在一条从根节点到叶子节点的路径使得路径上所有节点值相加等于 targetSum。这道题是递归回溯的经典入门题代码很短但隐藏的思维量很大。3.1 用「减法」思考比用「加法」更顺手我见过不少人的第一反应是递归时维护一个 sum每经过一个节点就把节点值加进去到叶子的时候判断 sum 是否等于 targetSum。这种加法思路完全可行但这意味着递归参数里要额外带一个累加值并且在递归返回后还要手动把累加值撤销回去——这就是显式回溯代码容易写乱。更推荐的写法是反向思维每递归一层就用 targetSum 减去当前节点的值。到叶子节点时只需要判断 targetSum 是否等于当前叶子节点的值。换句话说整个过程是在不断追问「从当前节点出发还差多少能凑够目标值」。class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root nullptr) return false; if (root-left nullptr root-right nullptr) { return targetSum root-val; } return hasPathSum(root-left, targetSum - root-val) || hasPathSum(root-right, targetSum - root-val); } };这里有个非常关键的点为什么减法写法不用显式回溯因为targetSum - root-val这个表达式作为参数传给子递归时它只是一个值副本并不会修改当前层的 targetSum。递归返回后当前层的 targetSum 还是原来的值自动就是「回溯后」的状态。这其实是一种隐式回溯——靠参数值传递天然实现不需要手动加加减减。很多刷题新手没想明白这一层就会在加法写法里为了回溯折腾半天。3.2 两个容易掉进去的坑第一个坑是「根到叶子」这个限定。题目要求的是根到叶子节点的路径所以终止条件必须是root-left nullptr root-right nullptr不能写成targetSum 0就提前返回。如果只判断targetSum root-val却不在叶子节点返回就会在非叶子节点提前得出 true比如一棵根节点值为5、左孩子为4的树targetSum 为5时原题答案是 false因为从根到左孩子再往下没有叶子了而错误写法会在根节点处直接判断 5 5 返回 true完全出错。第二个坑是空树的处理。root nullptr时要返回 false。有些版本会写成if (root nullptr) return targetSum 0;这在部分题目语境下能通过但在本题明确要求「根到叶子」的前提下空树没有叶子必须返回 false。这类边界条件看着不起眼实际测评时最容易翻车。3.3 为什么这道题看不出遍历顺序的影响还有一个值得想明白的问题这道题用前序、中序、后序都没区别为什么因为路径总和的判断逻辑完全依赖于「当前递归层处理当前节点的值」而节点本身的处理不依赖左右子树的中间结果也不涉及像中序遍历那样必须左中右严格排列的信息顺序。递归函数做的事就是「问左子树有没有可行路径问右子树有没有可行路径」这个结构本质上是一种自顶向下的分叉搜索先问哪边不影响最终答案。想通这一点就能理解为什么后面很多 DFS 题根本不在意用哪种遍历顺序。3.4 从 112 到 113 的扩展思路如果把题目改成「找出所有和为目标值的路径」LeetCode 113在 112 的基础上需要增加一个 path 数组在递归进入时把当前节点加入 path退出递归时从 path 末尾弹出。此时「显式回溯」就真正派上用场了——因为路径是全局共享的容器必须手动清理。所以 112 这道题其实是把「隐式回溯」和「显式回溯」的差别提前暴露给你理解了这一点后面做 113 会非常顺。4. 106.从中序与后序遍历序列构造二叉树分治的第一次实战这道题是二叉树章节里公认的硬骨头。给定一棵树的中序遍历序列和后序遍历序列要求还原出整棵二叉树。核心结论只有一个后序遍历的最后一个元素一定是根节点。一旦锁定根再回到中序遍历里找到根的位置根的左边就是左子树的中序序列根的右边就是右子树的中序序列。接着用左子树的长度去切分后序序列就能分别得到左子树和右子树的后序序列。然后递归重复这个过程。4.1 构建的整体思路以后序[9, 15, 7, 20, 3]和中序[9, 3, 15, 20, 7]为例。后序最后一个元素是3所以3是整棵树的根。在中序里找3下标为 1那么左子树的中序是[9]右子树的中序是[15, 20, 7]。因为中序左子树长度是 1后序里去掉最后一个根元素后前 1 个元素[9]就是左子树的后序剩下的[15, 7, 20]是右子树的后序。对左子树和右子树分别递归。整个过程中最隐蔽的坑就是第三步的后序切割后序左子树的长度完全由中序左子树的长度决定而不是想当然地取后序数组的前半段或均分。很多人第一次做这道题会试图按数组长度除以 2 切分这就是典型的错误思路。因为中序和后序来自同一个二叉树左右子树的节点数量必然一致所以必须用「中序根位置」作为两者的桥梁。4.2 用 vector 拷贝的直观写法先写一版最容易理解的实现直接切 vector 子数组虽然效率一般但逻辑直观class Solution { public: TreeNode* buildTree(vectorint inorder, vectorint postorder) { if (postorder.empty()) return nullptr; int rootVal postorder.back(); TreeNode* root new TreeNode(rootVal); if (postorder.size() 1) return root; int idx 0; for (int i 0; i inorder.size(); i) { if (inorder[i] rootVal) { idx i; break; } } vectorint leftInorder(inorder.begin(), inorder.begin() idx); vectorint rightInorder(inorder.begin() idx 1, inorder.end()); vectorint leftPostorder(postorder.begin(), postorder.begin() idx); vectorint rightPostorder(postorder.begin() idx, postorder.end() - 1); root-left buildTree(leftInorder, leftPostorder); root-right buildTree(rightInorder, rightPostorder); return root; } };几个细节值得说明为什么leftPostorder取的是postorder.begin()到postorder.begin() idx因为中序左子树的元素数量就是idx个下标 0 到 idx-1后序序列去掉根节点后前idx个元素恰好是左子树的后序。为什么rightPostorder是从postorder.begin() idx到postorder.end() - 1因为postorder.end() - 1位置上是根节点要排除掉而起点是左子树结束后的下一个元素。递归的终止条件有两个postorder.empty()对应空树postorder.size() 1对应只有一个节点的树。其实size() 1的情况也可以交给根节点建好后再递归处理但提前返回可以省两次子递归调用。4.3 用哈希表和下标索引的优化写法vector 拷贝写法的好处是好懂坏处是每次递归都要创建新数组空间和时间都有多余开销。面试时更推荐的写法是用下标区间在原数组上操作配合哈希表快速定位根节点在中序中的位置class Solution { public: unordered_mapint, int pos; TreeNode* build(vectorint inorder, vectorint postorder, int inL, int inR, int postL, int postR) { if (postL postR) return nullptr; int rootVal postorder[postR]; TreeNode* root new TreeNode(rootVal); int idx pos[rootVal]; int leftLen idx - inL; root-left build(inorder, postorder, inL, idx - 1, postL, postL leftLen - 1); root-right build(inorder, postorder, idx 1, inR, postL leftLen, postR - 1); return root; } TreeNode* buildTree(vectorint inorder, vectorint postorder) { for (int i 0; i inorder.size(); i) { pos[inorder[i]] i; } return build(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1); } };这套写法的核心是搞懂leftLen的语义idx - inL表示中序区间中根节点左边有多少个元素也就是左子树的规模。拿到这个值之后左右子树在四个数组区间里的边界就都确定了。这里的边界推导非常容易错我强烈建议自己动手画一遍中序左子树区间[inL, idx - 1]中序右子树区间[idx 1, inR]后序左子树区间[postL, postL leftLen - 1]后序右子树区间[postL leftLen, postR - 1]记住这个对应关系以后遇到 105前序中序构造二叉树也能一个套路迁移过去只是根节点的位置从前序区间的左端点开始找而已。4.4 为什么「前序后序」不能唯一确定一棵二叉树作为一种延伸我看很多讨论区都会提到这个问题既然中序后序可以构造中序前序也可以构造那前序后序行不行结论是不行。原因是前序的第一个元素和后序的最后一个元素都是根节点但仅仅知道根无法确定左子树是否存在。比如一棵只有左子树的树和一棵只有右子树的树它们的前序和后序序列是完全相同的。而中序序列提供了「左右子树分界线」这一关键信息所以才必须依赖中序参与构造。理解这一点也有助于记住 106 的解法不是后序让你能重建树而是「中序后序」的组合才能唯一确定树的结构。中序是定位左右子树的钥匙后序是提供根节点的来源两者缺一不可。5. 调试建议与常见错误复盘5.1 这道题组合里最常翻车的几个点我把三道题常见的错误汇总了一下写代码时可以在心里过一遍这份清单。513 用更新最大深度症状是返回的不是最左值而是最右值。排查时把判断改成严格即可。513 只在叶子节点更新但忘记保证左先于右如果先递归右孩子再递归左孩子结果就会变成最底层的「最右」节点。这是递归顺序的问题调换两行代码即可。112 没判断叶子节点就返回 true症状是 targetSum 等于某个非叶子节点值就提前返回 true。一定要检查root-left nullptr root-right nullptr这个终止条件。112 对负数剪枝我见过有人写if (targetSum 0) return false;来加速这种写法在节点值为负数时会出错因为可能当前 targetSum 小于 0但继续往下走加上负数后又能等于 0。所以路径总和这类题不能做简单的正负剪枝。106 切分后序右子树时起点算错这是最隐蔽的错。所有涉及切割区间的题都建议先在草稿纸上写出一个具体的小数组标出每个下标的位置再套进代码里验证一遍。106 递归终止条件只写postorder.empty()如果还同时用了下标索引要小心postL leftLen - 1这类表达式越界。终止条件写postL postR才能覆盖所有情况。5.2 学会用一个小用例手动走一遍递归遇到二叉树的递归题光靠脑子想很容易绕晕。我的调试习惯是拿一棵不超过 4 个节点的小树画出它的中序和后序序列然后手动模拟递归过程每一层在纸上写出inL/inR/postL/postR的数值变化。比如刚才那个用例模拟到某一步时发现postL竟然大于postR那就说明区间切分出了问题。这个方法虽然原始但比盯着屏幕看调试器高效得多尤其是 106 这种强索引计算的题目几乎每次都能靠笔头找出边界问题。5.3 三道题一起复习的节奏建议如果把这三道题放到一次完整的刷题计划里我建议是第一天先独立做一遍哪怕做不出来也要先看题思考十分钟第二天不看题解重写一遍重点检查递归终止条件和边界区间第三天再把这些代码和解题思路默写出来直到形成肌肉记忆。做完之后再配合 113、105、654最大二叉树这些同类型题目做横向对比你会发现很多套路其实是一通百通的。6. 一路刷下来的个人体会这三道题做完我最大的感受是二叉树刷题不要沉浸在「遍历模板写得多顺」里关键是要能把遍历过程中产生的信息利用起来。513 利用了深度信息和访问顺序112 利用了目标值在递归中的逐层传递106 利用了序列之间的长度对应关系。它们背后其实都是同一套东西——递归三要素想清楚终止条件写准确返回值或者参数里携带好状态信息。最后分享一个小技巧做这类二叉树题目时我每次都会在递归函数入口先写一句注释标明这个函数「接收什么、返回什么、在什么时候终止」。别看这只是注释它逼着我在动手写代码之前把逻辑理清楚很多边界问题在这一步就被提前消灭了。希望这篇内容对正在刷代码随想录第十六天的你有帮助如果哪道题卡住了可以把你的用例和输出贴出来一起讨论。