How do you handle leaf nodes in this problem?

When you reach a leaf node, you add the number formed by the current root-to-leaf path to the sum. This ensures that only complete paths contribute to the result.

What happens if the tree only has one node?

If the tree only contains one node, that node itself represents the sum. Since there are no other paths, the result will be just the value of that node.

What traversal pattern is best for this problem?

A depth-first search (DFS) traversal works best because it allows you to track the state (number formed) as you go down each path from root to leaf.

How does the recursive approach handle state tracking?

The recursive approach passes down the current number being formed at each step. When a leaf node is reached, the accumulated number is added to the total sum.

How would the complexity change if the tree had more than 1000 nodes?

If the tree had more than 1000 nodes, the time complexity would still be O(N), where N is the number of nodes. However, deeper trees may impact space complexity due to the increased recursion stack or iterative stack size.

#129

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。计算从根节点到叶节点生成的所有数字之和。叶节点是指没有子节点的节点。示例 1：输…

树深度优先搜索二叉树

题目描述

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

提示：

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

lightbulb

解题思路

方法一：DFS

我们可以设计一个函数 $dfs(root, s)$ ，表示从当前节点 $root$ 出发，且当前路径数字为 $s$ ，返回从当前节点到叶子节点的所有路径数字之和。那么答案就是 $dfs(root, 0)$ 。

函数 $dfs(root, s)$ 的计算如下：

如果当前节点 $root$ 为空，则返回 $0$ 。
否则，将当前节点的值加到 $s$ 中，即 $s = s \times 10 + root.val$ 。
如果当前节点是叶子节点，则返回 $s$ 。
否则，返回 $dfs(root.left, s) + dfs(root.right, s)$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是二叉树的节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root, s):
            if root is None:
                return 0
            s = s * 10 + root.val
            if root.left is None and root.right is None:
                return s
            return dfs(root.left, s) + dfs(root.right, s)

        return dfs(root, 0)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how DFS is applied to track root-to-leaf paths?
question_mark
Can you explain how you would modify your approach if the tree had more complex node values?
question_mark
Are you able to handle edge cases where the tree has only one node?

warning

常见陷阱

外企场景

error
Not properly tracking the current number as you traverse the tree, leading to incorrect sums.
error
Forgetting to add the number formed at the leaf node to the final sum.
error
Confusing binary-tree traversal approaches, such as mixing up DFS with BFS, or not accounting for recursion depth.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sum of all paths that lead to the leaf nodes of a n-ary tree.
arrow_right_alt
Calculate the product instead of the sum of root-to-leaf numbers in a binary tree.
arrow_right_alt
Find the maximum root-to-leaf number formed in a binary tree.

help

常见问题

外企场景

继续练习

#124 二叉树中的最大路径和 #117 填充每个节点的下一个右侧节点指针 II #116 填充每个节点的下一个右侧节点指针