DAY12: LeetCode 129｜求根节点到叶节点数字之和

LeetCode 129｜求根节点到叶节点数字之和

一、题目要做什么?

假设有这样一棵树：

4
/ \\
9 0
/ \\
5 1

这里的叶子节点是：5、1、0

所谓叶子节点，就是：

左孩子和右孩子都不存在的节点。

所以：

• 只有左孩子为空，不一定是叶子；
• 只有右孩子为空，也不一定是叶子；
• 必须左右孩子都为空，才是叶子。

题目要求我们从根节点开始，一直走到叶子节点。

于是这里一共有三条完整路径：

4 → 9 → 5

4 → 9 → 1

4 → 0

把经过的数字连起来，就得到：

495

491

40

最终：495 + 491 + 40 = 1026

所以这道题实际上需要解决两个问题：

二、先把问题缩小：如果只有一条路怎么办？

先假设树根本不会分叉，只有：4 → 9 → 5

那事情就很简单 :
初始：current_num = 0

• 来到 4：4
• 来到 9：4 × 10 + 9 = 49
• 来到 5：49 × 10 + 5 = 495

所以我们会发现一个规律。

每来到一个新的节点，只需要：之前的数字 × 10 + 当前节点的值

也就是：

current_num = current_num * 10 + node.val

所以，如果我们沿着一条路径往下走，就只需要记住一个东西：

到目前为止，这条路径已经组成了什么数字？

三、真正麻烦的地方：树会分叉

现实中的树不是：4 → 9 → 5 这么简单。

而是：

4
/ \\
9 0
/ \\
5 1

• 来到 4 以后，有两个方向：

  • 左边去 9。
  • 右边去 0。

• 来到 9 以后，又出现两个方向：

  • 左边去 5。
  • 右边去 1。

所以我们需要不断做这样一件事情：

来到一个节点
↓
处理当前节点
↓
看看下面还有没有节点
↓
如果还有，就继续处理它的孩子

🔖 但重点来了：

• 来到 4，需要做这些事情。
• 来到 9，也需要做这些事情。
• 来到 5、1、0，也都是面对同样的问题。

也就是说：

“处理当前这棵树”和 “处理它的左子树、右子树” 本质上是同一种问题。

这时候使用 递归 就很自然了。

因为递归特别适合处理这种：

大问题里面包含结构完全相同的小问题。

当然，这道题并不是只能递归。

也可以自己维护一个栈，用迭代 DFS 完成。

但这一篇先只讨论递归，因为递归最容易看清楚树的结构。

四、构建递归函数

前面我们已经知道：

这道题需要不断处理当前节点，然后继续处理它的左子树和右子树。

所以接下来，我们正式开始构建递归函数。

写一个递归函数时，可以先想几个最基本的问题：

我们就按照这个顺序来。

1. 递归函数需要哪些参数？

首先，我们肯定需要知道：

当前走到了哪个节点？

所以第一个参数是：node

但只有 node 还不够。

比如现在已经走到了：

4 → 9

来到节点 9 时，我们需要得到：49

但是 9 自己只知道：

node.val = 9

它还必须知道：

在来到我之前，这条路径已经组成了数字 4。

所以递归函数还需要额外保存：

当前路径已经组成的数字。

我们把它叫做：current_num

于是递归函数就可以定义成：

dfs(node, current_num)

其中：

node
→ 当前正在处理的节点

current_num
→ 来到当前节点之前，这条路径已经组成的数字

最开始还没有经过任何节点，所以第一次调用：

dfs(root, 0)

2. 进入一层递归后，先更新当前路径数字

假设当前调用：

dfs(9, 4)

表示来到节点 9 时，前面的路径已经组成数字 4。

根据前面总结的规律：

current_num = current_num * 10 + node.val

所以这一层更新后：

4 × 10 + 9 = 49

此时：

current_num = 49

3. 什么时候停止递归？

接下来要确定：

递归什么时候不需要再继续往下走？

这道题里有两种情况：

叶子节点

题目要求的是：根节点 → 叶子节点

所以只有走到 叶子节点，才说明一条完整路径真正形成 ->> 当前这条从根节点出发的路径已经走完了。

叶子节点指的是： 左孩子和右孩子都不存在的节点。

因此需要同时满足：

node.left is None and node.right is None

注意这里是 and。

只有左右两边都为空，当前节点才是叶子节点。

走到叶子以后返回什么？

比如当前路径是：

4 → 9 → 5

来到节点 5 后，我们已经计算出：

49 × 10 + 5 = 495

而节点 5 没有左右孩子，所以这条路径到这里正式结束。

此时：495 就是 这一条路径最终组成的数字。

因此直接返回当前的 current_num：

return current_num

一旦执行 return，当前这一层递归就结束了，不会再继续往下寻找子节点。

空节点

另一种停止递归的情况是：

当前这个方向根本没有节点。

例如：

1
/
2
\\
3

节点 2 不是叶子，因为它还有右孩子 3。

所以后面仍然需要继续处理它的左右两边。

但是往左走时会发现：

2 的左边是空的

既然这一边已经没有节点，就没有必要继续递归了。

因此遇到空节点时，可以直接返回：

return 0

为什么返回 0？

因为这一边没有形成任何完整路径，所以对最终结果没有贡献。

后面我们会把左右两边得到的结果相加：

左边结果 + 右边结果

如果左边不存在，那么：

0 + 右边真正的结果

不会影响右边的答案。

4. 如果未终止，就继续递归左右子树

假设现在来到节点 9：

9
/ \\
5 1

当前已经得到：

current_num = 49

但是节点 9 还有孩子，所以路径还没有结束。

接下来就需要继续处理它的左子树和右子树。

左边：

num_left = dfs(node.left, current_num)

也就是：

num_left = dfs(5, 49)

右边：

num_right = dfs(node.right, current_num)

也就是：

num_right = dfs(1, 49)

🚩 注意这里的代码执行顺序。

Python 会先执行：

dfs(5, 49)

只有等这个函数调用结束并且得到返回值以后：num_left 才会真正拿到结果。

然后程序才继续执行：

dfs(1, 49)

5. 递归函数到底返回什么？

这里是这道题最重要的地方之一。

我们需要先明确：

dfs(node, current_num) 的返回值到底代表什么？

可以把它定义成：

从当前节点继续往下走，所有完整路径最终组成的数字之和。

比如 节点 5：

4 → 9 → 5

只有这一条路径。

所以：

dfs(5, 49)

返回：495

节点 1：

4 → 9 → 1

也只有这一条路径。

所以：

dfs(1, 49)

返回：491

于是回到节点 9 以后：

num_left = 495
num_right = 491

那么节点 9 这一整棵子树下面，所有路径的总和 就是：

495 + 491 = 986

所以节点 9 最后返回：

return num_left + num_right

也就是：

return 986

return 495 为什么会回到节点 9？

因为节点 9 之前执行的是：

num_left = dfs(5, 49)

执行到这里时，节点 9 这一层的函数调用会暂时停下来。

程序进入：

dfs(5, 49)

节点 5 最后：

return 495

于是这个返回值会交回给调用它的位置：

num_left = dfs(5, 49)

因此：

num_left = 495

然后节点 9 这一层继续执行下一行：

num_right = dfs(1, 49)

这就是递归中的调用栈：

上一层函数调用下一层
↓
上一层暂停

下一层计算完成
↓
return 返回结果

上一层从刚才暂停的位置继续执行

五、把完整递归过程走一遍

现在再把整棵树跑一次：

4
/ \\
9 0
/ \\
5 1

🔵 第一次：

dfs(4, 0)

先处理节点 4：

current_num = 0 × 10 + 4
= 4

节点 4 不是叶子，所以继续处理左子树：

dfs(9, 4)

🔵 来到节点 9：

current_num = 4 × 10 + 9
= 49

节点 9 也不是叶子。

🟢 先处理左边：

dfs(5, 49)

来到节点 5：

current_num = 49 × 10 + 5
= 495

节点 5 是叶子：

return 495

回到节点 9：

num_left = 495

🟢 接下来处理右边：

dfs(1, 49)

来到节点 1：

current_num = 49 × 10 + 1
= 491

节点 1 是叶子：

return 491

回到节点 9：

num_right = 491

于是节点 9 汇总：

return 495 + 491

得到：986

🔵 这个 986 再返回节点 4：

num_left = 986

🟢 接下来节点 4 处理右边：

dfs(0, 4)

来到节点 0：

current_num = 4 × 10 + 0
= 40

节点 0 是叶子：

return 40

回到节点 4：

num_right = 40

最后节点 4 汇总：

return 986 + 40

最终得到：

1026

六、这道题的递归到底在做什么？

现在回头看，会发现这个递归其实有两个方向。

往下递归时：构造当前路径

例如：

4
↓
49
↓
495

我们不断更新：

current_num = current_num * 10 + node.val

所以：

路径状态在不断往下传。

往上返回时：汇总子树答案

叶子节点先返回：

495
491
40

然后：

495 + 491 = 986

最后：

986 + 40 = 1026

所以：

子树答案在不断往上收。

可以把这道题最核心的递归过程记成一句话：

状态往下传，答案往上收。

七、完整代码

等前面的递归过程想明白以后，再来看代码：

class Solution:
def sumNumbers(self, root: TreeNode | None) –> int:

def dfs(node, current_num):

# 当前分支没有节点
# 对最终结果没有贡献
if node is None:
return 0

# 先把当前节点加入路径数字
current_num = current_num * 10 + node.val

# 左右孩子都不存在
# 说明已经来到叶子节点
if node.left is None and node.right is None:
return current_num

# 递归处理左右子树
num_left = dfs(node.left, current_num)
num_right = dfs(node.right, current_num)

# 返回当前子树所有完整路径的数字之和
return num_left + num_right

return dfs(root, 0)

八、最后总结

这道题最开始并不需要直接想到完整代码。

可以一步一步拆：

第一步：
一条路径上的数字怎么构造？

current_num = current_num * 10 + node.val

然后发现树会不断分叉：

当前节点
↓
左子树
右子树

而每一棵子树面对的都是同样的问题，所以想到递归。

接着构建：

dfs(node, current_num)

其中：

node → 当前节点

current_num → 当前路径已经组成的数字

进入一层递归以后：

1. 先处理当前节点

2. 如果是叶子节点
→ 当前路径结束
→ 返回 current_num

3. 如果不是叶子
→ 递归左右子树

4. 等左右子树返回以后
→ 汇总结果
→ return num_left + num_right

所以最终可以把它理解成：

往下：
构造每一条路径对应的数字

往上：
把每一棵子树的答案逐层汇总

也就是：状态往下传，答案往上收。

九、复杂度分析

假设二叉树一共有 n 个节点。

时间复杂度：O(n)

递归过程中，每个节点只会被访问一次。

对于每个节点，我们做的操作也都是常数级的，例如：

current_num = current_num * 10 + node.val

以及判断是否为叶子节点。

所以总时间复杂度为：

O(n)

空间复杂度：O(h)

这里没有额外创建数组来保存所有路径，主要的空间开销来自递归调用栈。

其中 h 表示二叉树的高度。

如果树比较平衡：

1
/ \\
2 3
/ \\ / \\
…

树高大约是 log n，所以空间复杂度接近：

O(log n)

但如果树退化成一条链：

1
\\
2
\\
3
\\
4

递归最多会连续进入 n 层，因此最坏情况下：

O(n)

所以一般写成：

时间复杂度：O(n)
空间复杂度：O(h)，最坏情况下为 O(n)

十、其他两种实现方式

前面的核心思路其实已经确定了：

每往下一层，都需要保存当前路径已经组成的数字。

区别主要在于：

得到一条完整路径以后，我们准备怎么处理这个答案？

还可以有两种写法。

方法一：递归 + 直接累计答案

其实我们也可以换一种想法。

既然走到叶子节点时，就已经得到了一个完整数字，例如 495，那也可以不把它一层层 return 回去。

而是直接：

total += current_num

也就是：

往下递归
↓
构造 current_num
↓
来到叶子
↓
直接加入 total

代码：

class Solution:
def sumNumbers(self, root: TreeNode | None) –> int:

total = 0

def dfs(node, current_num):
nonlocal total

if node is None:
return

current_num = current_num * 10 + node.val

if node.left is None and node.right is None:
total += current_num
return

dfs(node.left, current_num)
dfs(node.right, current_num)

dfs(root, 0)

return total

复杂度同样是：

时间：O(n)
空间：O(h)

和第一种方法相比，区别在于：

方法一：

叶子
↓
return
↓
父节点汇总
↓
继续 return

方法二：

叶子
↓
直接加入 total

所以第二种不再需要：

return num_left + num_right

因为所有答案已经在叶子节点处直接累计起来了。

方法二：不用递归，自己维护栈

前两种方法都依赖递归。

但递归本质上会利用函数调用栈保存：

当前处理到哪里
以及这一层的状态

所以我们也可以自己创建一个栈，实现迭代版 DFS。

不过栈里面不能只保存：

node

因为只知道当前节点是谁还不够。

例如来到节点 9 时，我们还必须知道前面的路径已经组成了 4，才能继续得到 49。

因此栈中保存：

(node, current_num)

代码：

class Solution:
def sumNumbers(self, root: TreeNode | None) –> int:

if root is None:
return 0

total = 0

stack = [(root, 0)]

while stack:

node, current_num = stack.pop()

current_num = current_num * 10 + node.val

if node.left is None and node.right is None:
total += current_num
continue

if node.left is not None:
stack.append((node.left, current_num))

if node.right is not None:
stack.append((node.right, current_num))

return total

这里：

stack.pop()

体现的是栈的：

后进先出

所以它会沿着某一条路径不断往深处走，这就是 DFS。

复杂度：

时间：O(n)
空间：O(h)