做算法题的时候，经常碰到这么一种现象：一道题在编辑器里一跑就过，可要是让你关掉代码，在纸上把思路完整讲清楚，反而卡壳。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₂（5），cur * 2 = 1010₂（10），也就是把低位空出来。如果 v = 1，1010₂ + 1 = 1011₂；如果 v = 0，1010₂ + 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, val=0, left=None, right=None): 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₂（16），16 | 2= 18，16 + 2= 18，好像也相等？其实只要v是一个二进制位0/1会相等；v=2时不一定，比如cur=10010₂（18），左移一位100100₂（36），36 | 2 = 38，36 + 2 = 38，还是相等？不，36的二进制最低位是0，向左移动后空出的最低位一定是0，所以末位是0，按位或v的效果等于加v，只要v是任何末位为0的值且不超过……其实如果v是一个小于2的数？不对，v=2的二进制10，36 | 2最低两位10变10，加2也是把10加到最低两位。如果v=3呢？36 | 3 = 39，36 + 3 = 39。难道任意v都相等？不是的，这里涉及进位。比如cur=10000₂（16），左移一位100000₂（32），32 | 3 = 35，32 + 3 = 35。好像也相等，因为空出的低位都是0，没有进位冲突。但若v有跨位进位呢？v=3，从二进制看只影响最低两位，原低位为空，所以仍等价。那本质上只要左移后的最低若干位都是0，位或和加法等价。但若cur不是左移后的呢？或者v超过cur左移后可容纳的低位范围，例如v=5（101），cur=10000₂（16），左移后100000₂（32），32 | 5 = 32 | 0101 = 37，32 + 5 = 37，等价。只要是新空出的位都是0，加法没有进位链，位或等价于加法。但如果v = 0b1111_1111等，依旧等价，因为空出的低位位宽足够，且高一位起始也是0，没有从低位向高位进位的基础？似乎位或和加法在“被加数相应位全为0”时才算等价。所以我的说法“只在0/1下等价”不够严谨。更准确：因为这里的被加数 cur<<1 的低位全是0，而 node.val 只需要填一位，所以在本题二者等价。若 node.val 超过一位，最高位可能落在那位0上，如果没有后续进位链，如果它不超过二进制能容纳的位数，其实也会相等？比如v=2（10），被加数末位两个0，按位或 010 和 加法 010 相同。若v=6（110），被加数末三位为0，按位或 110 和加法 110 相同。若节点值超过空位宽度，比如v = 可以分解为高位的1和低位的组合，按位或只看每个位是否为1，没有进位，而加法在每一位上1+0=1也无进位，本质上只要被加数的对应位全是0，且v的每一位只作用在0位上，就不会进位，按位或等于加法。而cur << 1的最低若干位确实是0（取决于cur低位0的数量），但不能保证覆盖v的所有位。假如v=2（二进制10），cur<<1末位0但倒数第二位可能是1，比如cur=3（11），左移=110（6），6|2（10）=110|010=110=6，6+2=8，不相等！所以关键是cur左移后的低两位是否都为0。cur末位如果是1，左移后倒数第二位是1，这时 |2 会把那个1保留（110|010=110），而 +2 会产生进位（110+010=1000，8）。所以“只有0/1”确实是关键，因为cur左移后最低位一定为0，但次低位不一定为0，而v若不超过1，只影响最低位，所以等价。v=2就会影响次低位，可能不等价。所以原文说法是对的。我上面推36|2=36+2，因为36二进制100100，倒数第二位是0，没冲突。换个例子说明。不过本文是通俗文章，不需要展开到这个深度，只说“节点值只有0/1时才等价”即可。不要深入太多，避免跑题。

回到正文：采用哪种写法看个人习惯。我个人喜欢位运算写法，因为它更贴合“二进制数”这个语境，代码也简短。但如果你想让自己代码更容易被不懂位运算的人看懂，写cur * 2 + node.val完全没问题。真正加分的表现是，面试时能说出两者等价的条件以及背后的二进制原理。

3. 迭代实现：把递归的幕后工作搬到明面上

递归虽然好写，但很多场景下面试官会追问一句：“如果不让用递归，你打算怎么写？”这就是考察你对深度优先遍历和状态保存的掌握程度。

3.1 为什么要会写迭代版

第一个原因是避免递归栈溢出。在极端情况下，二叉树会退化成一条链，比如每个节点都只有右孩子，树高等于节点数。如果节点数以万计，递归深度也会以万计，某些语言默认栈空间不一定撑得住。第二个原因是面试场景。有些面试官故意限制递归写法，就是为了看你会不会用显式栈模拟系统调用栈。

迭代版的思想很简单：递归时，系统在调用栈里帮我们保存了“当前节点cur值”“左右子树是否访问过”等信息；迭代版则是自己用一个栈，把这些信息明确地存下来。最大的区别是，我们写代码的人必须自己决定栈里存什么、什么时候压入、什么时候弹出。

3.2 用栈存“节点+当前值”的一组完整代码

这里有一个非常推荐的做法：栈里同时存节点和“从根到这个节点已经形成的二进制值”。这样每个栈帧都是自包含的，弹出时不需要再额外查状态。

class TreeNode: def __init__(self, val=0, left=None, right=None): 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₂(n+1)，所以空间是 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^9+7 取模”。哪怕这道题不强制，提前掌握取模写法也没坏处。

10^9+7 是个很常用的模数。它是一个质数，而且足够大，在组合计数、哈希、动态规划里经常出现。对本题来说，我们只用了两种运算：乘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 代码时最常遇到的问题整理成了表格，按“症状 -> 原因 -> 修复”的格式看。

这些问题的共同根源，基本都在“状态建模不清晰”和“叶子结算条件不准确”这两件事上。你对照表里查一个，顺手把对应的函数签名和判断条件改掉，大多数情况都能解决。

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的基本功重新打磨了一遍。最后分享一个我常跟身边朋友提的小技巧：在纸上画一棵三层的二叉树，把每一条路径的二进制数字手算一遍，然后跟着代码里的每次递归调用走一遍状态变化。很多“递归想不明白”的问题，本质上不是递归难，而是你从来没亲手模拟过一遍状态变化。把这道题的每一行都吃透，后面再遇到类似的路径类题目，你会觉得它们全都在同一个框架里，只是换了层皮而已。