Medium

题目描述

给你一个二叉树的根节点 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

解题思路

解题思路

这是一个经典的二叉树遍历问题，需要计算从根到叶子节点所有路径形成的数字之和。

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

核心思想是在遍历过程中维护当前路径形成的数字。从根节点开始，每次向下遍历时，将当前数字乘以10再加上当前节点的值。当到达叶子节点时，将当前数字加入总和。

具体步骤：

  1. 从根节点开始DFS遍历
  2. 传递当前路径形成的数字（初始为0）
  3. 每访问一个节点，更新数字：current_num = current_num * 10 + node.val
  4. 如果是叶子节点，将当前数字加入结果
  5. 否则递归遍历左右子树

方法二：迭代遍历

使用栈或队列存储节点和对应的路径数字，本质与DFS相同但采用迭代实现。

时间复杂度：O(n)，其中n是节点数量，需要访问每个节点一次 空间复杂度：O(h)，其中h是树的高度，递归调用栈的深度

代码实现

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
    
private:
    int dfs(TreeNode* node, int currentNum) {
        if (!node) return 0;
        
        currentNum = currentNum * 10 + node->val;
        
        // 如果是叶子节点，返回当前数字
        if (!node->left && !node->right) {
            return currentNum;
        }
        
        // 递归计算左右子树的和
        return dfs(node->left, currentNum) + dfs(node->right, currentNum);
    }
};

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, current_num):
            if not node:
                return 0
            
            current_num = current_num * 10 + node.val
            
            # 如果是叶子节点，返回当前数字
            if not node.left and not node.right:
                return current_num
            
            # 递归计算左右子树的和
            return dfs(node.left, current_num) + dfs(node.right, current_num)
        
        return dfs(root, 0)

public class Solution {
    public int SumNumbers(TreeNode root) {
        return Dfs(root, 0);
    }
    
    private int Dfs(TreeNode node, int currentNum) {
        if (node == null) return 0;
        
        currentNum = currentNum * 10 + node.val;
        
        // 如果是叶子节点，返回当前数字
        if (node.left == null && node.right == null) {
            return currentNum;
        }
        
        // 递归计算左右子树的和
        return Dfs(node.left, currentNum) + Dfs(node.right, currentNum);
    }
}

var sumNumbers = function(root) {
    function dfs(node, currentNum) {
        if (!node) return 0;
        
        currentNum = currentNum * 10 + node.val;
        
        // 如果是叶子节点，返回当前数字
        if (!node.left && !node.right) {
            return currentNum;
        }
        
        // 递归计算左右子树的和
        return dfs(node.left, currentNum) + dfs(node.right, currentNum);
    }
    
    return dfs(root, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)n为二叉树节点数量，需要访问每个节点一次
空间复杂度O(h)h为二叉树高度，递归调用栈的最大深度

相关题目