LeetCode 第129题：求根节点到叶节点数字之和

题目描述

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

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

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

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

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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

解题思路

方法一：深度优先搜索（DFS）

这道题要求计算从根节点到所有叶节点路径表示的数字之和。我们可以使用深度优先搜索（DFS）来遍历二叉树的所有路径，并在遍历过程中计算路径表示的数字。

关键点：

使用DFS遍历二叉树的所有路径
在遍历过程中，维护当前路径表示的数字
当到达叶节点时，将当前路径表示的数字加入总和

具体步骤：

定义一个递归函数dfs(node, currentSum)，其中node是当前节点，currentSum是从根节点到当前节点路径表示的数字
如果node为空，返回0
计算当前路径表示的数字：currentSum = currentSum * 10 + node.val
如果node是叶节点（左右子节点都为空），返回currentSum
否则，返回dfs(node.left, currentSum) + dfs(node.right, currentSum)
调用dfs(root, 0)得到最终结果

时间复杂度：O(n)，其中n是二叉树的节点数，需要遍历所有节点。空间复杂度：O(h)，其中h是二叉树的高度，递归调用栈的最大深度为h。

方法二：广度优先搜索（BFS）

我们也可以使用广度优先搜索（BFS）来解决这个问题。BFS使用队列来存储节点和对应的路径数字。

关键点：

使用队列存储节点和对应的路径数字
当遇到叶节点时，将对应的路径数字加入总和
使用两个队列，分别存储节点和路径数字

具体步骤：

如果根节点为空，返回0
初始化总和sum为0
创建两个队列，nodeQueue存储节点，numQueue存储对应的路径数字
将根节点和根节点的值分别加入两个队列
进行BFS：
- 从nodeQueue中取出一个节点node，从numQueue中取出对应的路径数字num
- 如果node是叶节点，将num加入总和sum
- 如果node有左子节点，将左子节点和对应的路径数字(num * 10 + node.left.val)分别加入两个队列
- 如果node有右子节点，将右子节点和对应的路径数字(num * 10 + node.right.val)分别加入两个队列
返回总和sum

时间复杂度：O(n)，其中n是二叉树的节点数，需要遍历所有节点。空间复杂度：O(n)，队列中最多存储n个节点。

图解思路

DFS过程分析表

以示例1为例：root = [1,2,3]

节点	当前路径	当前数字	是否为叶节点	返回值	说明
1	[1]	1	否	25	根节点，继续递归
2	[1,2]	12	是	12	叶节点，返回12
3	[1,3]	13	是	13	叶节点，返回13

最终结果：12 + 13 = 25

BFS过程分析表

以示例1为例：root = [1,2,3]

步骤	节点队列	数字队列	当前节点	当前数字	是否为叶节点	总和	说明
1	[1]	[1]	-	-	-	0	初始状态
2	[2,3]	[12,13]	1	1	否	0	处理根节点
3	[3]	[13]	2	12	是	12	处理节点2，是叶节点，加入总和
4	[]	[]	3	13	是	25	处理节点3，是叶节点，加入总和

最终结果：25

代码实现

C# 实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int SumNumbers(TreeNode root) {
        return DFS(root, 0);
    }
    
    private int DFS(TreeNode node, int currentSum) {
        if (node == null) {
            return 0;
        }
        
        // 计算当前路径表示的数字
        currentSum = currentSum * 10 + node.val;
        
        // 如果是叶节点，返回当前路径表示的数字
        if (node.left == null && node.right == null) {
            return currentSum;
        }
        
        // 递归计算左右子树的路径数字之和
        return DFS(node.left, currentSum) + DFS(node.right, currentSum);
    }
}

Python 实现

# 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: TreeNode) -> int:
        def dfs(node, current_sum):
            if not node:
                return 0
            
            # 计算当前路径表示的数字
            current_sum = current_sum * 10 + node.val
            
            # 如果是叶节点，返回当前路径表示的数字
            if not node.left and not node.right:
                return current_sum
            
            # 递归计算左右子树的路径数字之和
            return dfs(node.left, current_sum) + dfs(node.right, current_sum)
        
        return dfs(root, 0)

C++ 实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
    
private:
    int dfs(TreeNode* node, int currentSum) {
        if (!node) {
            return 0;
        }
        
        // 计算当前路径表示的数字
        currentSum = currentSum * 10 + node->val;
        
        // 如果是叶节点，返回当前路径表示的数字
        if (!node->left && !node->right) {
            return currentSum;
        }
        
        // 递归计算左右子树的路径数字之和
        return dfs(node->left, currentSum) + dfs(node->right, currentSum);
    }
};

执行结果

C# 实现

执行用时：84 ms
内存消耗：38.9 MB

Python 实现

执行用时：32 ms
内存消耗：16.2 MB

C++ 实现

执行用时：0 ms
内存消耗：12.3 MB

性能对比

语言	执行用时	内存消耗	特点
C#	84 ms	38.9 MB	执行速度适中，内存消耗较高
Python	32 ms	16.2 MB	执行速度适中，内存消耗适中
C++	0 ms	12.3 MB	执行速度最快，内存消耗最低

代码亮点

🎯 使用DFS递归解决问题，代码简洁高效
💡 巧妙利用乘10加当前节点值的方式计算路径数字
🔍 递归函数返回值设计合理，便于计算总和
🎨 代码结构清晰，逻辑简单易懂

常见错误分析

🚫 没有正确处理空节点的情况
🚫 计算路径数字时没有乘以10，导致结果错误
🚫 没有正确判断叶节点（叶节点是左右子节点都为空的节点）
🚫 递归函数的返回值设计不合理，导致无法正确计算总和

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
DFS（递归）	O(n)	O(h)	代码简洁，思路清晰	递归调用可能导致栈溢出
DFS（迭代）	O(n)	O(h)	避免递归调用栈溢出	实现复杂，需要使用栈
BFS	O(n)	O(n)	适合处理层次遍历	实现稍复杂，需要使用队列

题目描述

难度

题目链接

示例

示例 1：

示例 2：

提示

解题思路

方法一：深度优先搜索（DFS）

方法二：广度优先搜索（BFS）

图解思路

DFS过程分析表

BFS过程分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目