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

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

🎯 问题描述

给你一个二叉树的根节点 root，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字（例如 1->2->3 表示数字 123）。计算从根节点到叶节点生成的所有数字之和。
说明： - 叶子节点是指没有子节点的节点。 - 路径数值的计算逻辑：每往下走一层，之前的数值 × 10 + 当前节点的数值。

• 示例：
• 示例 1：

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

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

  ## 💻 解题思路
  
  这道题的核心在于利用 DFS 遍历树，并在遍历过程中通过 `cr = cr * 10 + node.val` 动态构造路径数字。根据结果汇总方式的不同，可以分为两种经典的递归写法。
  
  ### 思路一：分治法（自底向上累加）
  **核心思想**：不依赖外部变量。每个递归函数负责计算“以当前节点为根的子树”的路径和，最后将左右子树的结果相加并返回给上一层。
  
  ```python
  class Solution:
      def sumNumbers(self, root: Optional[TreeNode]) -> int:
          def dfs(node, cr):
              if node is None:
                  return 0
              # 更新当前路径数字
              cr = cr * 10 + node.val
              # 如果是叶子节点，直接返回当前数字
              if not node.left and not node.right:
                  return cr
              # 否则，返回左右子树的路径和之和
              return dfs(node.left, cr) + dfs(node.right, cr)
          
          return dfs(root, 0)

思路二：全局变量法（自顶向下收集）

核心思想：利用外部变量 ans 记录总和。递归函数只负责“走路径”，当走到叶子节点时，将当前构造好的数字累加到全局变量中。

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node, cr):
            if node is None:
                return
            nonlocal ans  # 声明使用外部变量
            cr = cr * 10 + node.val
            # 走到叶子节点，将当前数字累加到总和中
            if not node.left and not node.right:
                ans += cr
            # 继续向左右子树遍历
            dfs(node.left, cr)
            dfs(node.right, cr)
        
        dfs(root, 0)
        return ans

📊 性能分析

• 时间复杂度：$O(n)$。两种方法都需要遍历二叉树的所有节点各一次。
• 空间复杂度：$O(h)$。取决于递归调用栈的深度，即二叉树的高度 $h$。

💡 总结与对比

• 思路一（返回值累加）：代码更纯粹，没有副作用，是函数式编程中更推崇的写法，也是二叉树算法题中最经典的递归范式。
• 思路二（全局变量收集）：逻辑更符合直觉（找到了就加进去），在处理“统计个数”、“收集路径列表”等变种题目时非常实用。