1. 从训练营第十四天说起两道题背后的共同考点代码随想录训练营走到第十四天二叉树专题已经进入了一个微妙的阶段基础的三种遍历前中后序和层序遍历大家都已经练过一轮递归函数的基本框架也搭得差不多了。这时候突然甩出513.找树左下角的值和112.路径总和这两道题很多人一开始会觉得“这不就是遍历题吗有什么难的”——然后一写就卡住。实际上这两道题正好踩中了二叉树学习里最核心也最容易混淆的两个点一是递归与回溯的关系二是深度优先和广度优先的适用场景。如果你只是机械地背模板碰到这种需要自己设计递归参数、自己控制回溯时机的题目很容易写出“运行结果碰巧对了但换个输入就错”的代码。这篇博文会把两道题从题意拆解、递归设计、迭代实现到常见坑点完整捋一遍特别适合正在刷代码随想录、或者刚刚进入二叉树刷题阶段的朋友。我自己在训练营里做这两道题的时候也踩了不少坑文中会把这些实际教训一并放进来希望能帮你少走弯路。2. 找树左下角的值一次看懂“递归回溯”与“层序遍历”两条路2.1 先别急着写代码把“左下角”定义清楚513题的要求很简短给定一个二叉树的根节点返回该树最底层的最左边节点的值。注意这里的限定条件是两个缺一不可必须是最深的那一层同时必须是该层最左侧的节点。这里有个很经典的误解。很多人看到“最左边”就以为要一路往左走到叶子其实不是。题目说的是“整棵树最后一行的最左边”也就是说如果最后一层有好几个节点取的是这一层里最靠左的那一个。它不是一条路径上的节点而是层级的属性。这个定义直接决定了两种主流解法一种在递归里记录“当前深度”并不断刷新结果另一种在层序遍历里按行扫描并记录每行第一个节点。理解了这层含义之后你会发现这道题本质上考的是在遍历过程中跟踪“深度信息”的能力而不是单纯的查找。2.2 递归解法最大深度的“赛马”机制递归解法的核心思想可以用一句话概括**用深度优先遍历扫过整棵树每遇到一个叶子节点就对比一下它的深度如果比之前记录的最大深度还大就更新结果。**因为先序遍历的顺序是“中→左→右”在同一层里左边的节点总是先于右边的节点被访问到所以只要在“深度变深”的那一刻记录节点值最后留下的必然是底层最左侧的节点。直接上代码C版class Solution { public: int maxDepth -1; // 当前遇到的最大深度 int result; // 对应那个深度的节点值 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) { depth; // 进入左子树深度加一 traversal(node-left, depth); depth--; // 回溯恢复深度 } if (node-right) { depth; traversal(node-right, depth); depth--; } } int findBottomLeftValue(TreeNode* root) { traversal(root, 0); return result; } };这里最值得琢磨的就是depth和depth--这一对操作。为什么不能直接传depth 1其实也可以写成traversal(node-left, depth 1)的话函数内部不会修改当前层的 depth 变量也就不需要手动回溯。但很多教材和题解习惯写成“先改再传、传完再改回来”目的是为了让你直观地看到回溯动作发生在递归返回之后。我建议初学者在纸上画一个三层的小树手动模拟一遍这段代码的执行顺序。你会发现每从递归深处返回一层depth 变量就恢复成这一层原本的值这样才能保证每个兄弟节点都在正确的深度上被比较。这个“深度的现场保护”就是回溯的本质。2.3 迭代解法层序遍历的“降维打击”如果说递归解法考验的是对深度的敏感度那迭代解法就是考验你对 BFS广度优先搜索的理解。思路非常简单用队列进行层序遍历每一层都从第一个节点开始处理把这个节点的值记下来等整个队列清空的时候最后一次记录的值就是树左下角的值。class Solution { public: int findBottomLeftValue(TreeNode* root) { queueTreeNode* que; if (root) que.push(root); int result 0; while (!que.empty()) { int size que.size(); for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); if (i 0) { result node-val; // 每一层的第一个节点 } if (node-left) que.push(node-left); if (node-right) que.push(node-right); } } return result; } };这段代码里有个小技巧for循环开始前先取size que.size()这样就把“当前层的节点数”固定住了循环内部入队的节点属于下一层不会影响本层的遍历。这是层序遍历题目里的标准操作代码随想录里也反复强调过。还有另一种迭代写法入队时先放右孩子再放左孩子这样队列里弹出的最后一个节点就是左下角的节点。两种写法的本质一样我个人更推荐上面这种“记录每层第一个节点”的版本因为它的语义更直观上一层的第一个节点会被下一层的第一个节点覆盖走到最后一层留下来的自然是整棵树的左下角。2.4 两种解法怎么选放到面试场景里迭代解法通常更稳不用考虑递归深度也不会因为回溯逻辑写错而翻车。但递归解法也绝不能不会写因为很多二叉树题目比如路径总和天然适合递归思路递归是你理解问题的第一工具迭代只是实现手段。从训练角度说这道题最好的练法是两种解法都写一遍并且想想为什么递归里需要回溯参数而迭代里不需要。想通了这一点你对“层的概念”和“深度的概念”会有一次质的飞跃。3. 路径总和递归回溯的“精简版实战”3.1 题意拆解要找的是“存在性”而不是“所有路径”112题的要求是给定一个二叉树和一个目标整数判断这棵树里是否存在一条从根节点到叶子节点的路径使得路径上所有节点值之和等于目标值。注意这里的关键词是“是否存在”不是“找出所有路径”。这意味着你只需要返回一个布尔值一旦找到一条满足条件的路径就可以立即终止搜索。这个“找到就停”的特点决定了递归函数可以设计成“带短路返回”的形式。另外还有个边界含糊的地方题目说的是“根节点到叶子节点”叶子节点指没有子节点的节点。所以如果根节点只有一个孩子路径必须走到那个孩子为止不能中途停在一个非叶子节点上就算数。这个细节是很多人写错的第一道坎。3.2 递归解法用“递减计数”代替“求和比较”常见的直观思路是从根开始累加路径和等到了叶子节点再跟 targetSum 比较。这种写法当然可以但会导致递归参数变多、代码变长。代码随想录里推荐了一种更简洁的思路把目标和当作计数器每经过一个节点就减去它的值到叶子节点时判断计数器是否刚好归零。class Solution { public: bool traversal(TreeNode* node, int count) { // 叶子节点判断路径和是否等于目标值 if (node-left nullptr node-right nullptr) { return count 0; } if (node-left) { count - node-left-val; if (traversal(node-left, count)) return true; count node-left-val; // 回溯 } if (node-right) { count - node-right-val; if (traversal(node-right, count)) return true; count node-right-val; // 回溯 } return false; } bool hasPathSum(TreeNode* root, int targetSum) { if (root nullptr) return false; return traversal(root, targetSum - root-val); } };这段代码里有两个点必须讲清楚。第一为什么入口要传targetSum - root-val而不是直接传targetSum因为递归函数内部统一处理的是“到当前节点为止还剩余多少目标值”这样在进入左/右孩子时只需要减去孩子的值即可判断叶子节点时也只要看 count 是不是 0逻辑非常统一。如果入口直接传 targetSum那递归内部就必须先判断“当前节点要不要算进路径”会平白多出很多条件分支。第二递归里的回溯为什么是count node-left-val这跟 513 题的depth--是同一个道理——递归返回后需要恢复调用前的状态否则右边兄弟节点收到的 count 就是被左子树“污染”过的值。你可以试试把回溯那行注释掉多半会得到错误答案因为递归进入左子树后count 变小了回到当前层时没有恢复接着进右子树时初始值就不对了。3.3 迭代解法用栈保存“节点累计值”如果不想用递归迭代解法需要额外存储一个状态当前节点以及走到这个节点时的路径和。栈里存pairTreeNode*, int就能实现。class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root nullptr) return false; stackpairTreeNode*, int st; st.push(pairTreeNode*, int(root, root-val)); while (!st.empty()) { pairTreeNode*, int cur st.top(); st.pop(); if (cur.first-left nullptr cur.first-right nullptr) { if (cur.second targetSum) return true; } if (cur.first-right) { st.push(pairTreeNode*, int(cur.first-right, cur.second cur.first-right-val)); } if (cur.first-left) { st.push(pairTreeNode*, int(cur.first-left, cur.second cur.first-left-val)); } } return false; } };这里有个细节值得注意入栈顺序我写了“先右后左”。因为栈是后进先出的先压右子树再压左子树弹出时左子树会先被处理。这道题只关心存在性左右顺序无所谓但如果题目改成“按路径顺序输出所有满足条件的路径”这个顺序就会影响结果输出。刷题时养成习惯是好事后面做 113题路径总和II 时你会在意到这一点。3.4 路径总和里的经典边界坑我在训练营里看到不少人在同一类边界条件上翻车下面这几种情况值得单独拎出来说一下。空树的情况。root nullptr时直接返回 false因为不存在任何节点也就没有路径。这个好理解但容易漏。单支树的情况。假设树只有一个左孩子一路延伸右孩子全是空。递归到叶子节点时如果 count 正好是 0 就返回 true。但注意别把“非叶子节点但只有一个孩子”的状态当成叶子。判断叶子必须同时满足两个 child 都为 null。负数目标值的情况。题目里的节点值和目标值可能是负数所以不能进行“剪枝优化”比如if (count 0) return false——这种优化只在所有值为正时成立。我在代码里没有加剪枝就是为了保证负数值场景下依然正确。很多初次刷题的同学会下意识加一个“count 小于零直接返回”的逻辑这在 LeetCode 的部分用例上会直接挂掉。4. 回溯的精髓告别“背模板”理解状态恢复这两道题放在同一天做其实有一个很刻意的安排它们都需要在递归里做状态回溯。513 回溯的是深度112 回溯的是计数器。把它们放在一起对比你会发现回溯的本质根本不是“某个知识点”而是一句大白话递归调用是一层层的“下潜”当你从深处浮上来时必须把现场恢复成下潜之前的样子。4.1 为什么递归天然需要回溯先看一个反例。假设你不回溯直接把代码写成if (node-left) { depth; traversal(node-left, depth); } if (node-right) { depth; traversal(node-right, depth); }这会导致什么问题当左子树的递归结束返回当前层时depth 已经变成了“左子树深处的深度”紧接着进入右子树时右子树的起点深度就错了。这个错误不是某个分支的偶然偏差而是会让整个深度比较全部乱套。你要是把这种写法套到 112 题count 同样会被左子树“透支”右子树的剩余目标值就少算了一段。回溯的本质就是把变量恢复到函数调用前的值。在这个语境下depth--和count node-left-val做的都是同一件事。4.2 参数传递的艺术值传递与引用传递很多初学者会困惑为什么有时候递归函数不写回溯也能对答案藏在参数的传递方式里。如果你在递归函数签名里把参数写成值传递比如void traversal(TreeNode* node, int depth) // depth 是值传递那每次递归调用都会拷贝一份 depth 的副本函数内部怎么改都不影响上一层。这时候确实不需要手动回溯。如果写成引用传递void traversal(TreeNode* node, int depth)那所有递归层共享同一个 depth 变量就必须要手动回溯。但这里的坑在于有些题目用值传递会导致空间浪费有些写法用引用传递则必须先回溯。刷题时我个人的习惯是递归参数用值传递能少写回溯就少写但是如果需要“共享一个集合”来记录路径——比如后面 113 题要收集所有满足条件的路径——就必须用引用传递并配合回溯。这不是玄学核心判断标准只有一条你这个变量是“每一层独立的标尺”还是“所有层共享的结果容器”。4.3 从二叉树到组合问题的思维迁移回溯这个能力一旦在二叉树里练通后面做回溯算法章节组合、排列、子集问题会特别顺。组合问题里的path.pop_back()和这里的depth--、count val本质上是同一个动作。代码随想录的训练营里经常有人问“为什么组合问题要先 push 再递归再 pop”其实二叉树这两道题已经把答案展示过了你进入一个分支之前先标记路径离开这个分支之后撤销标记这样每条分支才能拿到干净的初始状态。所以我强烈建议如果你今天做完这两道题觉得回溯很绕别急着看后面的回溯专题先回头把这篇文章里的两道题亲手多写两遍尤其是把递归展开的调用栈画出来比刷十个新题都管用。5. 刷题过程中的典型问题与排查经验5.1 513题结果对但顺序错问题多半出在“更新时机”我在训练营群里看到过一个挺典型的 bug同学用递归写 513但是把更新结果的操作放在了进入左右子树之前。这样会导致什么问题想象一棵三层树根节点在第一层第二层有两个子节点第三层左边有值右边也有值。如果你的代码在每进入一个节点时就更新result和maxDepth那走到第二层右边的节点时 maxDepth 已经是 2第三层左边节点再进来时是 3确实能覆盖。但如果有左右子树深度不一样的情况比如左子树只有一层、右子树有三层那么你会先记录左子树第二层的节点再记录右子树第三层的节点最后留下的确实是最底层的最左节点碰巧是对的。但如果你把 maxDepth 初始值设为 0而树的根节点本身没有子节点只有根节点那么你永远不会在叶子节点处更新 result因为根节点也是叶子但判断逻辑可能漏掉根节点。这里我要专门强调513 里根节点本身就是叶子节点的情况一定要单独确认代码逻辑覆盖到了。我的递归写法在叶子节点判断里统一处理了根节点但如果你把更新操作放在左右子树递归分支内部根节点就会被漏掉。排查这类问题有个高效手段打印递归进入和退出的每个节点值以及当前深度。一旦你看到某个叶子节点的深度比 maxDepth 大但 result 没有更新那就是更新时机的问题。5.2 112题为什么“找到了 true 却总被覆盖成 false”这个问题的根源是递归函数返回值的处理方式。看下面这段错误示例bool traversal(TreeNode* node, int count) { if (!node-left !node-right) return count 0; bool leftOK false, rightOK false; if (node-left) { count - node-left-val; leftOK traversal(node-left, count); count node-left-val; } if (node-right) { count - node-right-val; rightOK traversal(node-right, count); count node-right-val; } return leftOK || rightOK; }这段代码本身其实是对的但有人会在递归调用后不加判断直接返回比如写成return traversal(node-left, count) || traversal(node-right, count);如果左子树返回 false右子树返回 true那整体确实是 true没问题。问题出在另一种写法先递归左子树然后把左子树结果存下来如果为 true 就直接向上返回 true否则再递归右子树。如果没有“找到就返回”的短路逻辑即使左子树已经找到了满足条件的路径代码还是会继续递归右子树最终返回的结果取决于右子树。虽然布尔逻辑的或操作能兜底但右子树的递归会造成额外开销更重要的是它容易掩盖你对回溯时机的理解偏差。我的建议是递归返回值涉及“存在性”判断时一旦得到 true立即 return不需要继续探索。代码随想录的题解也是这个风格因为这才是符合实际语义的写法“存在一条路就够了”。5.3 迭代写法的常见错位层序遍历的 size 丢失513 题迭代解法里int size que.size()必须放在for循环外部。我见过有同学习惯性写成for (int i 0; i que.size(); i)这在层序遍历里是严重的 bug因为循环内不停往队列推入子节点que.size()会持续变化导致原本只有两个节点的当前层被循环处理了四次甚至更多。同样的错误也会出现在 112 的迭代解法里——不过 112 的迭代不用层序遍历用的是栈模拟 DFS没有这个 size 问题。但如果你把 513 的迭代解法延伸到其他层序遍历题比如 102 二叉树的层序遍历、199 二叉树的右视图这个 size 固定手法是标配必须做到条件反射级熟练。5.4 递归状态打印大法如果你被某份递归代码绕晕了最快的调试方式是加一个全局变量记录当前递归深度然后在函数入口打印深度和节点值在出口再打印一次。比如void traversal(TreeNode* node, int depth) { cout enter node node-val at depth depth endl; // ... cout exit node node-val at depth depth endl; }用这种办法你能非常直观地看到每一个调用层级之间的关系也能看到 depth 参数在回溯前后是否保持一致。刷 513 和 112 时只要会打印这个状态基本没有解不开的谜。我自己的习惯是先把递归调用的“入口状态”打印出来跑一遍小规模用例确认顺序和纸上模拟一致再把打印删掉。这个方法在后来的回溯算法章节救了我无数次。6. 刷完这两道题后我还想多说几句代码随想录训练营第十四天的内容到这里就算完整覆盖了513 让你掌握“深度跟踪 回溯”和层序遍历两种面112 让你体会“计数器递减 短路返回”的递归设计。这两道题做完后面迎接你的就是更大的硬骨头——比如 113 路径总和II要把所有满足条件的路径都收集起来、437 路径总和III允许路径不上始于根以及各种需要构建二叉树的题目。我自己做这两道题时的最大体会是不要死记“递归三步曲”要理解每一步是在回答什么问题。递归函数的返回值是什么参数里哪些是需要更新的状态终止条件真的终止了吗这三个问题想清楚大部分二叉树递归题都能自己推出来。最后分享一个具体的小技巧刷题时给每个递归函数都问一句“如果不回溯输出会怎么变”。你可以故意删掉回溯代码跑一遍用例亲眼看看错误长什么样。这个过程看起来有点反直觉但只要你见过一次“少了回溯导致答案漂移”的现象后面基本再也不会忘记写回溯了。