递归算法刷题真正让人上头的往往不是递归本身而是递归边界那几行代码。求根节点到叶节点数字之和就是一道特别典型的题代码量不大、递归框架清晰可每次总有人在终止条件和递推公式上栽跟头。这道题问的是一棵二叉树里所有从根到叶子的路径分别能被拼成一个十进制数再把所有这样的数加起来是多少。比如根节点是1左孩子是2右孩子是3那么两条路径对应12和13答案就是25。看似只是把路径逐段拼接其实背后藏着二叉树递归最核心的写法之一用参数把路径信息一路传下去。对于正在学递归、或者准备面试想巩固树的DFS遍历的朋友这道题非常适合作为练手素材它把“递推公式 边界判断”这两件事讲得明明白白。1. 思路定调为什么这个题天生适合递归1.1 先把题意拆开揉碎题目输入是一棵二叉树每个节点上有一个0到9的数字。要求计算所有从根节点到叶子节点的路径所表示的数字之和。这里的“路径所表示的数字”是逐层拼接出来的根节点是最左边的高位叶子节点是个位。举个例子给一棵这样的树4 / \ 9 0 / \ 5 1从根到叶一共有三条路径4 - 9 - 5拼出来是4954 - 9 - 1拼出来是4914 - 0拼出来是40三条路径的数字相加495 491 40 1026这就是答案。很多新手看到“数字之和”会下意识以为要对每个节点的值求和其实不是。这里加的是“一整条路径拼成的数字”而不是单个节点值。也就是说每一层的节点值对最终结果的贡献权重不一样越靠近根部的节点权重越大。1.2 数字拼接的本质乘以10再加当前值从数学上看把一个新节点追加到路径末尾本质就是把之前的数字往左挪一位即乘以10然后加上当前节点的值。假设走到某个节点时父节点那边已经拼好的数字是prevSum那么当前节点作为路径末尾产生的数字就是curSum prevSum * 10 node.val这个式子就是整道题的灵魂递推公式。它看起来简单但几乎所有解法都是围绕它展开的不管是递归、迭代还是层序遍历底层都是这条公式在工作。用生活中的例子来理解好比你在填写一个多位数每走到树的一层相当于在数字末尾多写一位数字。原来是12多了一位3就变成123数学操作就是12 × 10 3。这是十进制本身的位权规则也是这道题和“从根到叶路径”这个概念绑定最深的地方。1.3 为什么优先选择递归而不是循环二叉树本身就是递归定义的一棵树由根节点、左子树、右子树组成而左子树和右子树各自又是一棵树。所以遍历树的天然方式就是递归——写起来顺逻辑上也贴合树的结构。这道题要求“从根到叶子的路径”在深度优先搜索的递归过程中天然就是沿着一条路径往下钻的。走到叶子时这条路径的完整数字已经在参数里攒好了直接返回即可。相比显式地维护栈结构递归省去了手动管理状态的开销代码的可读性也高很多。当然递归不是唯一答案。面试里如果被追问“能不能用迭代实现”也需要能写出来。但作为解题第一版递归是最直观、最容易讲清楚的方案。这也符合一般做题的节奏先递归再谈优化不要一开始就绕进迭代状态管理里。2. 递归主解法把当前数字一路传下去2.1 核心递推公式与递归语义写递归函数之前先明确这个函数到底“返回什么”。这里我定义一个辅助函数dfs(node, prevSum)它表示从根节点到node的父节点已经形成的数字是prevSum这个函数返回的是“以node为起点所有能走到叶子的路径数字之和”。在这个语义下递推关系非常清楚先通过 prevSum × 10 node.val 算出当前路径数字curSum如果node本身就是叶子左右孩子都为空直接返回curSum否则结果等于左子树的递归结果加上右子树的递归结果空节点时返回0因为空节点代表这棵子树里没有合法路径不贡献任何数字。这里有一点需要特别说明很多人写空节点判断时会写“if not node: return 0”然后顺手在叶子节点也这样处理结果发现所有路径和都是0因为叶子节点会被当成左右孩子为空的两个空节点根本轮不到把curSum返回出去。叶子判断必须写在空节点判断之后、递归调用之前。2.2 标准参考代码Python版本class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def sumNumbers(root): def dfs(node, prevSum): if not node: return 0 curSum prevSum * 10 node.val if not node.left and not node.right: return curSum return dfs(node.left, curSum) dfs(node.right, curSum) return dfs(root, 0)C版本逻辑完全一致class Solution { public: int sumNumbers(TreeNode* root) { return dfs(root, 0); } int dfs(TreeNode* node, int prevSum) { if (!node) return 0; int curSum prevSum * 10 node.val; if (!node-left !node-right) return curSum; return dfs(node-left, curSum) dfs(node-right, curSum); } };代码就这么短但每一个分支都有存在的理由。root传入空树时dfs(root, 0)返回0只有一个根节点时curSum等于node.val直接返回有左右孩子时两棵子树的结果互不干扰最后相加。2.3 为什么参数传递天然免去了显式回溯同样是一道树的DFS题如果题目要求收集所有路径很多人会写一个全局path数组然后递归前进时push回溯时pop。那样做需要非常小心回溯的时机写漏一行就全乱了。但这道题用参数传递curSum每次递归调用都生成一个独立的局部变量下层函数修改它不会影响上层函数的值。这种设计天然就是“可回溯”的递归返回后当前层的prevSum还是原来的值不需要任何额外清理操作。可以把这个参数想象成接力棒每一层拿到接力棒算出自己的新数字curSum然后传给下一层。下一层传完就结束了无需把接力棒再带回来。这种思路在动态规划类递归题目里同样常见把“累积值”当作不可变参数传递代码最稳。2.4 对比全局变量回溯写法有经验的同学会把答案累积到一个全局变量里def sumNumbers(root): ans 0 pathSum 0 def dfs(node): nonlocal ans, pathSum if not node: return pathSum pathSum * 10 node.val if not node.left and not node.right: ans pathSum dfs(node.left) dfs(node.right) pathSum // 10 dfs(root) return ans这种写法在逻辑上等价核心动作是进入节点时更新pathSum到达叶子时累加进ans递归返回后把pathSum的最后一位去掉回溯。它的优点是省去了“每层都返回一个数再相加”的过程缺点也很明显——必须记住回溯而且一旦在某个分支提前return忘记回溯就会污染接下来的路径。用参数传递的方式就没有这些问题我强烈建议新手优先掌握参数传递写法它更安全也更贴合“函数式”的思维每个递归调用只关心自己的输入输出不共享状态。3. 边界条件与易错点全记录3.1 三类典型边界条件边界条件直接影响递归函数是否正确也是这类题的送分题和送命题。第一空树。root为null时没有任何路径答案应该是0。这个一般不会错但要注意不要在空树上取root.val那会直接报空指针异常。第二只有一个根节点。此时根节点既是根又是叶子递归函数会直接走到叶子判断返回root.val。比如[1]答案是1。如果这时候你的代码把空节点判断写在了叶子判断前面并且没有对根节点单独做处理很容易变成返回0。第三单链树。比如每个节点只有左孩子路径只有一条递归会把整条链走完最后在唯一叶子处返回路径数字。这种情况下递归深度等于节点数量如果树特别深需要考虑是否会出现栈溢出。比赛中一般不会特意卡这个但心里要有数。3.2 我踩过的三个坑第一个坑把叶子节点判断写成“if not node.left or not node.right”。这是逻辑错误会把“有一个孩子为空”的中间节点错认为是叶子。必须用and即左右孩子都为空才算叶子。第二个坑在叶子节点返回后忘记对非叶节点做空子树过滤。比如递归调用时直接写dfs(node.left, curSum)但node.left可能为空所以函数开头必须处理空节点否则下一层访问node.val时就会报错。第三个坑测试时只测了满二叉树没有测只有右子树或只有左子树的情况。这类倾斜树最容易暴露回溯和空判断的问题。拿到题目后先在心里构造一棵只有左孩子的树跑一遍递推过程基本就能发现80%的边界问题。3.3 手工推演一个完整案例拿前面那棵树重新推演一遍4 / \ 9 0 / \ 5 1调用dfs(root, 0)进入根节点4curSum 0 * 10 4 4不是叶子进入左子树dfs(节点9, 4)curSum 4 * 10 9 49不是叶子进入左子树dfs(节点5, 49)curSum 49 * 10 5 495叶子返回495进入右子树dfs(节点1, 49)curSum 49 * 10 1 491叶子返回491返回495 491 986进入右子树dfs(节点0, 4)curSum 4 * 10 0 40叶子返回40返回986 40 1026整个过程就是一路往下乘10加数字到叶子时停止再把所有叶子路径的数字累加。推演一遍之后再看代码就会觉得每个分支都顺理成章。3.4 测试用例速查表输入树预期输出说明null0空树[1]1单节点[1,2,3]25两条路径12和13[1,2]12只有左孩子[1,null,3]13只有右孩子[4,9,0,5,1]1026多路径相加[0,1]1根节点为0时前缀0不改变数值最后一种情况值得多说一句如果根节点是0路径“0-1”拼出来是01十进制还是1。加上0乘以任何数还是0所以数字前缀0不影响结果这个点也体现出直接用数学乘法处理的优势如果先转字符串再转数字反而要额外处理前导零。4. 不用递归也能解栈与队列的两种替代方案4.1 显式栈手动模拟深度优先递归背后的本质是函数调用栈所以完全可以用自定义栈模拟同样的流程。栈里每个元素保存两个信息当前节点、走到该节点时已经拼接好的数字pathSum。每从栈里弹出一个节点先计算它对应的curSum如果它是叶子就把curSum累加到答案里否则把左右孩子连同各自的curSum压栈。Python参考代码def sumNumbers(root): if not root: return 0 total 0 stack [(root, root.val)] while stack: node, pathSum stack.pop() if not node.left and not node.right: total pathSum continue if node.right: stack.append((node.right, pathSum * 10 node.right.val)) if node.left: stack.append((node.left, pathSum * 10 node.left.val)) return total这里有一个压栈顺序的细节先压右孩子再压左孩子出栈时就会先处理左孩子。如果你希望严格按照“从左到右”的路径顺序遍历整棵树就保持这个顺序如果顺序无所谓怎么压都行。反正最后是求和先后顺序不影响结果。栈版本的代码量比递归多一点但好处是摆脱了系统递归深度限制。对于特别深的树使用显式栈更稳健。4.2 层序队列换个角度遍历如果不用DFS也可以用BFS的层序遍历来做。区别在于DFS是一条路走到黑再回头BFS是一层一层推进但每个节点依然要携带自己的路径数字信息。用队列实现from collections import deque def sumNumbers(root): if not root: return 0 total 0 queue deque([(root, root.val)]) while queue: node, pathSum queue.popleft() if not node.left and not node.right: total pathSum if node.left: queue.append((node.left, pathSum * 10 node.left.val)) if node.right: queue.append((node.right, pathSum * 10 node.right.val)) return totalBFS的思路是把每个节点所在的路径数字算出来存入队列等它出现在队首时直接判断叶子并累加。由于层序遍历会同时处理多个分支队列的空间复杂度在最坏情况下是二叉树的宽度比递归的深度更耗空间。满二叉树最后一层节点数是2^(h-1)这可不是一个小数目。4.3 三种方式对比实现方式数据结构遍历顺序空间复杂度最坏情况代码简洁度递归系统调用栈深度优先O(h)最简洁显式栈自定义栈深度优先O(h)中等队列队列广度优先O(2^h)中等三种方法的时间复杂度都是O(n)每个节点恰好访问一次。空间上递归和显式栈都取决于树的高度h最坏情况下树退化成链表h等于n队列则取决于树的宽度最坏情况出现在满二叉树的底层。面试时如果被问“递归的缺点是什么”可以从“调用栈深度受限”和“函数调用开销”两个角度回答再顺势给出栈版本作为优化方案会显得思路非常完整。5. 复杂度、溢出与同类型题扩展5.1 时间复杂度和空间复杂度怎么算时间上每个节点只被递归函数进入一次所以总时间就是节点数n记为O(n)。空间上递归过程中系统栈的最大深度等于树的高度h。完美平衡二叉树的高度约等于log n空间复杂度就是O(log n)最坏情况下树是一条单链高度等于n空间复杂度退化为O(n)。很多人会忽略一个细节虽然时间上是O(n)但每层递归里有一次乘法、一次加法这些常数操作同样会影响实际运行速度。这个问题规模一般不大常数差异可以忽略但如果面试时随口说“递归比迭代快”那就说反了——递归有函数调用开销通常比显式迭代要慢一点点。5.2 关于整型溢出的提醒题目里节点值是0到9理论上如果树很深拼出来的数字可能超过int范围。比如一棵20层的满二叉树最长的路径数字会超过int上限。很多在线判题不会刻意构造这种数据但作为工程实践C里可以用long long来接中间结果或者在做乘法前先判断一下if (prevSum (INT_MAX - node-val) / 10) { // 已经溢出可以按题目要求处理或转用更大类型 }如果面试官特意问到这个问题能主动提一句“这里要考虑整型溢出的可能性生产环境建议用64位整数”会是一个不错的加分项。5.3 从这道题延伸出去的递归题型“求根节点到叶节点数字之和”是一个很典型的路径类问题和它同源的相关题型不少。第一路径总和问题。判断是否存在一条从根到叶子的路径使得路径上的节点值之和等于给定的target。这个题的递归框架几乎一模一样只是把“乘以10再加val”换成了“累加val”终止条件同样是叶子判断。第二输出所有路径。要求输出所有根到叶子的路径比如“1-2-3”。这种题就需要额外的path数组保存过程递归返回时要pop属于需要显式回溯的题型。第三求最大路径和。这个变体更难一点因为路径不一定要从根出发而是可以在任意节点之间。此时递归函数返回的含义就要做调整不再是“根到当前节点”而是“以当前节点为端点向上延伸能得到的最大和”思路转向后续遍历。把这些题目放在一起看会发现它们共享同一个DFS骨架进入节点时更新状态叶子节点时收集结果递归返回时根据需求决定是否回溯。理解了这道题等于给这类路径问题打了个好底子。最后说几句实际操作中的体会我第一次做这道题的时候写出来的版本在叶子节点判断那里漏掉了对curSum的返回导致整棵树的答案全是0排查了很久才意识到问题出在边界分支上。后来养成一个习惯凡是树的递归题先写空节点判断再写叶子判断最后才写左右子树的递归调用这个顺序固定下来之后出错率明显下降。顺带分享一个小技巧在本地调试时可以自己写一个从数组构造二叉树的辅助函数把输入转换成树结构再配合print语句观察每次递归进入节点时的prevSum。打印几轮之后递推公式和边界到底哪里有问题一眼就能看出来。这道题的代码量不大但覆盖的知识点很密递归语义、递推公式、叶子判断、参数传值、回溯比较、复杂度分析、甚至还有溢出处理。把这些点吃透收获的不仅是一道题的解法更是后面做所有树的路径类问题时的通用思维框架。