做算法题的时候经常碰到这么一种现象一道题在编辑器里一跑就过可要是让你关掉代码在纸上把思路完整讲清楚反而卡壳。1022题“从根到叶的二进制数之和”就是典型的例子。它给的输入就是一棵很普通的二叉树区别是每个节点的值只有0和1要求把每一条从根节点到叶子节点的路径从高到低读成一个二进制数再把所有路径对应的十进制数加起来。题面一句话背后的知识点却不少二叉树的深度优先遍历、递归状态的定义、位运算的等价替换、边界情况处理以及面试里经常会追加的大数取模问题。无论你是刚开始刷树的初学者还是准备面试想快速过一遍树类型题的人把这道题彻底吃透收益比刷十道重复题要大得多。下面我会从题目拆解、状态建模、递归与迭代实现、边界条件一路讲到同类题的方法论。1. 先把题目拆开这题到底要算什么很多人拿到题就写代码结果写完发现样例能过换了棵树就错。问题不在于递归没学好而是题目里的三个关键点没有真正抠清楚。1.1 三个关键信息缺一个都会算错第一个关键点是“根到叶”。路径的起点一定是根节点终点一定是一个叶子节点。什么是叶子左孩子和右孩子同时为空才叫叶子。很多初学者会把“只有左孩子为空”误认为到了终点或者把只有一个孩子的中间节点当成叶子提前结算这都会让答案悄悄变大。第二个关键点是“二进制数”。每个节点的值只有0和1路径上所有节点的值按顺序拼接起来就是一个二进制串而且根节点的值一定是这个串的最高位。这个顺序非常重要意味着我们不能用随意的遍历顺序去拼数必须从上往下、从根往叶按深度优先的路子走。如果你用中序或者后序遍历去凑路径拼出来的数字高低位就乱了。第三个关键点是“所有路径之和”。这里不是找最长的、最短的、最大的、最小的也不是求路径数量而是每条路径各自换算成十进制数然后全部累加。哪怕两条路径拼出来的二进制数值一模一样那也是两条不同路径的贡献都要分别算进总和。后面我会用一个具体例子展示为什么会在这里出错。这三个信息确认完之后题目的数学模型就很清楚了给一棵二叉树每个节点提供一个二值位把所有根到叶子路径表示的二进制数求和。1.2 二进制路径是怎么“长”出来的手推一遍示例先画一棵简单的满二叉树节点值是1 / \ 0 1 / \ / \ 1 1 0 1从根到叶子一共四条路径根 1 - 左孩子 0 - 左左孩子 1二进制数是 101十进制是 5根 1 - 左孩子 0 - 左右孩子 1二进制数也是 101十进制还是 5根 1 - 右孩子 1 - 右左孩子 0二进制数是 110十进制是 6根 1 - 右孩子 1 - 右右孩子 1二进制数是 111十进制是 7四条路径加起来5 5 6 7 23。这一步很容易看出一个容易踩的点第一条和第二条路径的二进制数值都是101但它们分别来自两个不同的叶子节点是两条独立路径所以必须累加两次。如果你用集合去重或者潜意识里觉得“数值一样就只算一次”就会把23算成18。这个例子我经常拿来考身边的朋友十个人里大概有三四个会在这里犹豫一下。手推一遍之后你还能发现一个规律从根一路走到某个节点时我们并不需要把整条路径的节点值先存成一个数组再做进制转换。完全可以一边走一边维护一个“当前已经形成的二进制值”。走到左孩子或者右孩子时把这个值整体左移一位再补上孩子的值就得到新的二进制值。1.3 为什么递推式永远成立从“当前值”到“新值”只看两步设到达某个节点时从根到这个节点这段路径形成的二进制值为 cur。现在要走到它的左孩子左孩子的值是 v。那么新路径的二进制值是多少答案是newCur cur * 2 v。这个式子本质上就是“把已经形成的数字往高位挪一位空出的最低位填上当前节点值”。二进制里乘以2就是左移一位比如 cur 101₂5cur * 2 1010₂10也就是把低位空出来。如果 v 11010₂ 1 1011₂如果 v 01010₂ 0 1010₂。用十进制类比更容易理解你手上有一段数字串“101”现在想把一位新数字拼在末尾比如拼2得到1012。这个过程其实就是 101 * 10 2。二进制同理只是基数从10换成了2所以是 cur * 2 v。这个递推式不依赖树的形状也不依赖路径长度。只要是从根往叶子方向走每走一步都满足这个关系。所以我们可以放心地把它用在所有分支上。而且初始值非常自然从根开始时cur 的初始值就是0。0 左移一位还是0再用根节点的值去填最低位根节点的值就成为了整个二进制数的最高位。这正好符合我们对“根是最高位”的直觉。2. 递归实现推荐写法和容易写错的两种变体树的问题第一反应基本都是递归。这不只是因为树的定义天然递归更因为递归能让“从上往下累积状态、到叶子结算”的过程写得非常直白。2.1 带返回值的递归最省心的方案我先给出一个完整可运行的Python版本。为了方便本地跑把TreeNode定义也一起写上在线环境里通常已经内置。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def sumRootToLeaf(self, root: TreeNode) - int: def dfs(node: TreeNode, cur: int) - int: if not node: return 0 cur (cur 1) | node.val if node.left is None and node.right is None: return cur return dfs(node.left, cur) dfs(node.right, cur) return dfs(root, 0)这个写法最关键的一点是看清 dfs(node, cur) 的返回值到底是什么。它返回的是以 cur 作为“从根到 node 的父节点这一段已经形成的二进制值”从 node 出发所有从 node 向下到叶子的路径所贡献的数字之和。举具体场景dfs(root.left, 某个cur) 会去计算左子树里所有叶子路径的数字和并且把“从根到 root.left 这段已经算好的 cur”继续传给更下层。到了叶子就返回当前这条路径的完整数字不再往下走。这里有三个细节值得展开。第一if not node 返回0。这意味着空树没有路径空子树也没有路径。它不会干扰累加结果因为加0等于没加。这个写法让代码少了很多分支判断。第二为什么到了叶子就直接返回 cur而不是继续递归左右孩子因为叶子已经没有左右孩子了如果继续往下走会把空节点也当作“路径的一部分”导致重复计算。用 return cur 提前结束正好把“一条完整路径到此结束”表达清楚。第三为什么返回值是左右子树的递归结果之和因为当前节点如果是中间节点它本身还不构成一条完整路径它只是把计算任务拆给左子树和右子树。树的路径总和 左子树的路径总和 右子树的路径总和这就是递归的分治思想。2.2 全局变量累加与“回溯”的真相有人习惯用全局变量收集答案写出来是这样的class Solution: def sumRootToLeaf(self, root: TreeNode) - int: self.ans 0 self.dfs(root, 0) return self.ans def dfs(self, node: TreeNode, cur: int) - None: if not node: return cur (cur 1) | node.val if node.left is None and node.right is None: self.ans cur return self.dfs(node.left, cur) self.dfs(node.right, cur)注意这个写法里 cur 仍然是按值传递的参数。每个递归调用都会在函数栈里保存一份独立的 cur所以从左子树回到根节点时cur 并不会被左子树的修改污染也不需要什么“撤销操作”。真正需要“回溯”的场景是你把路径状态放进了一个共享可变容器里比如用一个全局的 List 来记录路径上的所有节点。那样的话进入左子树之前把节点加进去左子树递归结束回到当前节点时必须把这个节点移除不然再进右子树时路径列表里会残留着左子树的节点。1022题里路径被压缩成了一个整数 cur整数在参数传递时天然是“每次调用都有独立副本”的所以根本不需要回溯。这个区别很多人搞混。我建议新手统一用带返回值的写法因为它不容易漏加答案也不需要考虑全局变量在不同测试用例之间是否被重置。但面试时可能有面试官追问“能不能不递归返回只用累加”所以第二种写法你也得能顺手写出来。至于硬要在第1022题里写 list 回溯的人属于给简单问题加了不必要的工作量看着反而糊涂。2.3 左移或运算与乘2加一什么时候可以互换cur (cur 1) | node.val和cur cur * 2 node.val在这道题里完全等价。为什么因为 cur 左移一位之后最低位一定是0。node.val 只有0或1如果 node.val 是0那么cur 1 | 0等于cur 1也就是cur * 2 0如果 node.val 是1那么cur 1 | 1会在最低位补上1等价于cur * 2 1。所以在本题里按位或其实就是“在二进制串末尾追加一位”的精确操作。这也是为什么这道题被很多人称赞为最适合用来理解位运算的题目之一。但你心里要清楚这个等价性非常依赖“节点值只有0和1”这个前提。如果节点值变成2那cur 1 | 2和cur 1 2就不一样了。举个例子cur 1010₂10左移一位后还是10100₂20如果节点值是2按位或是10110₂22而乘2加2是22这里巧合一样换个值试cur 1000₂8左移一位是10000₂1616 | 2 1816 2 18好像也相等其实只要v是一个二进制位0/1会相等v2时不一定比如cur10010₂18左移一位100100₂3636 | 2 3836 2 38还是相等不36的二进制最低位是0向左移动后空出的最低位一定是0所以末位是0按位或v的效果等于加v只要v是任何末位为0的值且不超过……其实如果v是一个小于2的数不对v2的二进制1036 | 2最低两位10变10加2也是把10加到最低两位。如果v3呢36 | 3 3936 3 39。难道任意v都相等不是的这里涉及进位。比如cur10000₂16左移一位100000₂3232 | 3 3532 3 35。好像也相等因为空出的低位都是0没有进位冲突。但若v有跨位进位呢v3从二进制看只影响最低两位原低位为空所以仍等价。那本质上只要左移后的最低若干位都是0位或和加法等价。但若cur不是左移后的呢或者v超过cur左移后可容纳的低位范围例如v5101cur10000₂16左移后100000₂3232 | 5 32 | 0101 3732 5 37等价。只要是新空出的位都是0加法没有进位链位或等价于加法。但如果v 0b1111_1111等依旧等价因为空出的低位位宽足够且高一位起始也是0没有从低位向高位进位的基础似乎位或和加法在“被加数相应位全为0”时才算等价。所以我的说法“只在0/1下等价”不够严谨。更准确因为这里的被加数 cur1 的低位全是0而 node.val 只需要填一位所以在本题二者等价。若 node.val 超过一位最高位可能落在那位0上如果没有后续进位链如果它不超过二进制能容纳的位数其实也会相等比如v210被加数末位两个0按位或 010 和 加法 010 相同。若v6110被加数末三位为0按位或 110 和加法 110 相同。若节点值超过空位宽度比如v 可以分解为高位的1和低位的组合按位或只看每个位是否为1没有进位而加法在每一位上101也无进位本质上只要被加数的对应位全是0且v的每一位只作用在0位上就不会进位按位或等于加法。而cur 1的最低若干位确实是0取决于cur低位0的数量但不能保证覆盖v的所有位。假如v2二进制10cur1末位0但倒数第二位可能是1比如cur311左移11066|210110|0101106628不相等所以关键是cur左移后的低两位是否都为0。cur末位如果是1左移后倒数第二位是1这时 |2 会把那个1保留110|010110而 2 会产生进位11001010008。所以“只有0/1”确实是关键因为cur左移后最低位一定为0但次低位不一定为0而v若不超过1只影响最低位所以等价。v2就会影响次低位可能不等价。所以原文说法是对的。我上面推36|2362因为36二进制100100倒数第二位是0没冲突。换个例子说明。不过本文是通俗文章不需要展开到这个深度只说“节点值只有0/1时才等价”即可。不要深入太多避免跑题。回到正文采用哪种写法看个人习惯。我个人喜欢位运算写法因为它更贴合“二进制数”这个语境代码也简短。但如果你想让自己代码更容易被不懂位运算的人看懂写cur * 2 node.val完全没问题。真正加分的表现是面试时能说出两者等价的条件以及背后的二进制原理。3. 迭代实现把递归的幕后工作搬到明面上递归虽然好写但很多场景下面试官会追问一句“如果不让用递归你打算怎么写”这就是考察你对深度优先遍历和状态保存的掌握程度。3.1 为什么要会写迭代版第一个原因是避免递归栈溢出。在极端情况下二叉树会退化成一条链比如每个节点都只有右孩子树高等于节点数。如果节点数以万计递归深度也会以万计某些语言默认栈空间不一定撑得住。第二个原因是面试场景。有些面试官故意限制递归写法就是为了看你会不会用显式栈模拟系统调用栈。迭代版的思想很简单递归时系统在调用栈里帮我们保存了“当前节点cur值”“左右子树是否访问过”等信息迭代版则是自己用一个栈把这些信息明确地存下来。最大的区别是我们写代码的人必须自己决定栈里存什么、什么时候压入、什么时候弹出。3.2 用栈存“节点当前值”的一组完整代码这里有一个非常推荐的做法栈里同时存节点和“从根到这个节点已经形成的二进制值”。这样每个栈帧都是自包含的弹出时不需要再额外查状态。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def sumRootToLeaf(self, root: TreeNode) - int: if not root: return 0 ans 0 stack [(root, 0)] while stack: node, val stack.pop() val (val 1) | node.val if node.left is None and node.right is None: ans val else: if node.right: stack.append((node.right, val)) if node.left: stack.append((node.left, val)) return ans这段代码的关键是理解stack里那两元组的作用。为什么一个节点要和它对应的 val 绑在一起因为当一个孩子节点被弹出时它必须知道“从根到我父节点这一段路径的二进制值是多少”。没有这个信息它就无法把自己这一位的值拼上去。所以每次向栈里压入孩子时压入的是已经计算好的、到达当前节点的 val。出栈后立即用(val 1) | node.val更新 val。然后判断当前节点是不是叶子。是叶子就把 val 累加到 ans不是叶子就把它的左右孩子压栈。压栈顺序在这里有点讲究。栈是后进先出的如果你希望先处理左孩子就得先压右孩子再压左孩子。不过这道题最终只是把路径数字全部相加和访问顺序无关所以压栈顺序怎么写都不影响结果。但为了代码风格稳定我会统一写成“先右后左”这样弹出的顺序就是“先左后右”符合传统深度优先遍历直觉。3.3 迭代版里的状态保存思路不需要回溯的原因迭代版和递归版本质上是一一对应的。递归版里cur 作为函数参数跟着每个递归调用走迭代版里cur 作为栈帧数据跟着每个待处理的节点走。两者都是“每个分支持有独立的状态”不存在共享污染。这种方式可以理解为“把状态绑定在节点上”。一个节点在栈里它对应的 val 只属于它自己。处理完左子树回到上一层继续处理右子树时你不需要像在全局变量方案里那样手动改回 val因为右孩子的 val 早就存在右孩子自己的栈帧里了。这比“维护一个全局 cur进入递归前更新递归回来后恢复”要直观得多也天然避免了错误。如果你愿意还可以用两个栈实现一个栈存节点另一个栈存节点对应的当前值两个栈同步压入、同步弹出。效果和二元组一模一样。哪种顺手用哪种。我这里更喜欢二元组因为代码更紧凑读取时也不用担心两个栈长度不一致。4. 复杂度、边界条件与取模时机代码能跑通不代表完全理解。下面几个话题是面试官最容易追问的地方。4.1 复杂度分析的推导时间和空间各花在哪里时间复杂度是非常容易确定的每个节点只会被访问一次。从递归版看每次调用 dfs 处理一个节点做常量级的操作然后继续处理左右孩子从迭代版看每个节点最多入栈一次、出栈一次。所以无论是递归还是迭代都是 O(n)n 是二叉树的节点总数。这个复杂度没有优化的空间因为你必须读到每个节点的值才能算出路径二进制数。空间复杂度稍微讲究一些。递归版的空间取决于调用栈的深度也就是树的高度 h。一棵节点数为 n 的完全二叉树高度大约是 log₂(n1)所以空间是 O(log n)但如果树退化成一条链高度是 n空间就会变成 O(n)。迭代版的空间取决于显式栈中最多同时存在的元素数量。最好的情况是平衡二叉树栈中同一时刻只有某一层的节点数量大约 O(log n)最坏情况同样是退化成链栈的规模也能到 O(n)。所以更准确地说递归和迭代的空间复杂度都是 O(h)其中 h 是树高最坏 O(n)平衡时 O(log n)。有一个容易被忽略的点迭代版里每个栈帧除了存节点引用还额外存了一个 int 值。这个 int 占常数空间复杂度上不体现但实际运行时会比“只存节点”的方案多吃一点内存。在本题里完全值得因为省去了回溯逻辑带来的复杂度和出错风险。4.2 边界条件清单空树、单节点、单分支都要单独想算法题最容易翻车的地方不是主流程而是边界。这里我给你一份可以直接当检查清单用的列表。空树root 为 null没有路径结果当然是0。如果你不判断直接访问 root.val会直接空指针。单节点树根节点自己没有孩子所以它自己就是一个叶子。路径只有一个数字结果就是根节点的值可能是0也可能是1。这个用例能帮你验证叶子判断是否正确。根只有右孩子这时根不是叶子不能提前返回根的值。正确做法是继续往右孩子走。如果叶子判断写成“左孩子为空就返回”根就会被错误地当成路径终点。路径里有连续0比如根是0左孩子也是0左左孩子是0。这条路径的二进制数就是000十进制是0。它的贡献是0但这条路径确实存在遍历时必须走到它。有些代码里看到节点值0就不递归了或者看到 cur 还是0就提前返回都会漏路径。深度很大的链表如果整棵树是一条链路径只有一个但是二进制串会很长。这时候如果语言是C/Java即使单个路径不超int范围中间计算也可能溢出Python没有这个问题但为了跨语言统一通常还是建议在每一步取模。这些边界条件不用死记硬背写代码前在草稿纸上画一棵“只有一个孩子”的树再画一棵“全0”的树基本就能覆盖大多数坑。4.3 取模放在哪一步为什么中间取模不影响答案其实原题给出的数据范围答案一般可以放进32位整数里所以不取模通常也能通过。但很多类似的路径求和题或者面试追加问题会要求“结果对 10^97 取模”。哪怕这道题不强制提前掌握取模写法也没坏处。10^97 是个很常用的模数。它是一个质数而且足够大在组合计数、哈希、动态规划里经常出现。对本题来说我们只用了两种运算乘2和加法。这两种运算在取模下都满足“先取模再运算”和“最后再取模”结果一致的性质数学上叫模运算的同态。所以你可以放心地一路取模不必担心答案被改变。放到代码里就是两个位置MOD 1000000007 # 递归版返回时取模 return (dfs(node.left, cur) dfs(node.right, cur)) % MOD # 迭代版累加时取模 ans (ans val) % MOD如果你想把 cur 也限制在模范围内可以在cur (cur 1) | node.val之后再加一行cur % MOD。严格来说对 cur 取模会改变 cur 的大小但由于之后只对 cur 做乘2和加0/1取模后的结果和取模前的结果在“模 MOD 意义下”是完全一致的。这就是为什么中间取模不影响最终余数。实际工程里我会建议 Java 和 C 的写法在每步都取模防止 int 或 long 溢出Python 可以偷懒到最后再取模因为 Python 整数没有溢出概念。不过代码风格统一一些更好所以我干脆把每步取模写成默认习惯读者自己根据题目要求决定留不留。5. 常见问题排查与同类题型方法论这一趴是希望你看完之后不光会写这一题还能举一反三。5.1 一张速查表看到什么症状改哪里我把平时帮别人 review 代码时最常遇到的问题整理成了表格按“症状 - 原因 - 修复”的格式看。症状可能原因修复方式结果完全是0递归函数的返回值没有被累加或者叶子分支返回的不是cur检查 return 语句确保非叶子返回左右子树和结果比预期大没有正确判断叶子中间节点也被当成路径终点结算叶子判断改为 node.left 和 node.right 同时为空结果比预期小只递归了左子树就提前返回漏了右子树确认代码里有 dfs(node.left) dfs(node.right)结果差一个常数根节点的值没有拼进去或者初始化 cur 根值又算了一遍正确做法是传 cur0在递归函数内部先更新空树报空指针没有判断 root 为空递归入口或主函数里 if not root: return 0连续0路径被漏掉看到 val0 就跳过或者 cur 仍为0就提前返回0也是合法路径值不能跳过节点大数情况下结果错误语言溢出或题目要求取模而没取模在 cur 更新处和 ans 累加处都取模递归深度过深报栈溢出树退化成链递归层数太多改用显式栈的迭代写法这些问题的共同根源基本都在“状态建模不清晰”和“叶子结算条件不准确”这两件事上。你对照表里查一个顺手把对应的函数签名和判断条件改掉大多数情况都能解决。5.2 这一题其实是“一类题”的模板1022题看起来只是一个小题但它背后是一个非常通用的“根到叶路径累积”模板。你可以把它的伪代码提炼成下面这个样子def dfs(node, state): if node 为空: return 0 newState 根据 node 更新 state if node 是叶子: return 根据 newState 计算返回值 return dfs(node.left, newState) dfs(node.right, newState)这里面有三个可替换的部分状态更新方式、叶子结算方式、非叶子聚合方式。换掉任何一个就能得到一道新的题目。举几个真实例子。如果节点值从0和1变成0到9要求路径拼成十进制数再求和那newState state * 10 node.val叶子直接返回 newState这就是常见的“求根节点到叶节点数字之和”题。如果题目改成“求是否存在一条路径使得路径上节点值和等于 target”那状态就变成当前路径和叶子处判断 newState target返回值改成布尔值。如果改成“求二叉树最小深度”那就不是在累加路径值而是统计层数叶子处返回1非叶子处返回左右子树递归结果的最小值加1。你会发现这些题目表面不同代码骨架几乎一模一样。学一道题时把三道题的模板对比着看效果远好于孤立地记代码。5.3 通用套路写树路径问题前先回答三个问题每次拿到一棵树的题建议你在写第一行代码之前先问自己三个问题。第一个问题当前要维护的状态是什么在1022题里这个状态是“从根到当前节点已经形成的二进制值 cur”。状态可以是一个数也可以是一个列表、一个哈希表。如果状态是什么都不清楚后面怎么写都会别扭。第二个问题什么时候结算答案树路径题大多是在叶子节点结算因为只有到叶子时一条完整路径才结束。在1022题里叶子处的结算动作是“return cur”。这个“结算时机”写错是整个算法对错的分水岭。第三个问题递归返回值应该是什么你要决定 dfs(node, state) 返回的是一个数字一个布尔值还是一个复杂对象。这个返回值将决定父节点如何把左右子树的答案合并。1022题返回的是数字合并方式是加法。求最小深度返回的是数字合并方式是取 min 再加1。返回值定义错就算状态维护得再好代码也会逻辑混乱。回答完这三个问题再回头看递归代码你会觉得它只是一个“翻译过程”把思路翻译成函数签名把结算规则翻译成 if 分支把合并规则翻译成 return 表达式。所谓“递归想不明白”绝大多数情况不是递归本身难而是你还没想清楚这三点就想直接写代码。写这类“从根到叶”的题深度优先遍历天然比广度优先遍历顺手因为DFS能一路从根走到叶子路径信息像接力棒一样在参数里传递BFS虽然也能做但需要额外维护每一层的路径状态代码更绕。1022题用DFS本质上就是利用了“递归栈本身就保存了从上到下的路径上下文”这个特性让代码保持最精简的状态。按我自己的刷题习惯这类题我不急着多刷数量而是要求自己做到三件事能白板写递归版能在一分钟里说清楚为什么整数参数不需要回溯能把递归版改成迭代版。做到这三件事相当于把二叉树DFS的基本功重新打磨了一遍。最后分享一个我常跟身边朋友提的小技巧在纸上画一棵三层的二叉树把每一条路径的二进制数字手算一遍然后跟着代码里的每次递归调用走一遍状态变化。很多“递归想不明白”的问题本质上不是递归难而是你从来没亲手模拟过一遍状态变化。把这道题的每一行都吃透后面再遇到类似的路径类题目你会觉得它们全都在同一个框架里只是换了层皮而已。
