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

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

示例：
输入：root = [1,2,3]
输出：25
解释：
路径 1->2 代表数字 12，路径 1->3 代表数字 13，总和 = 12 + 13 = 25。

解题过程
本题目标是遍历所有从根到叶子的路径，将路径上的节点值拼接成数字，最后返回这些数字的总和。这本质上是树的深度优先搜索（DFS）问题，在遍历过程中需要记录当前路径的数值。

步骤1：理解数字的拼接方式
假设当前路径已经表示数值 prevSum，现在遇到一个新节点，节点值为 node.val。那么新的数值应该是 prevSum * 10 + node.val。
例如，路径 1->2 的数值计算过程：

• 到节点1：0*10 + 1 = 1
• 到节点2：1*10 + 2 = 12

步骤2：确定搜索思路
从根节点开始深度优先遍历，每深入一层，就更新当前路径表示的数值。当到达叶子节点（没有左右子节点）时，说明一条完整路径形成，此时将当前数值累加到总和中。

步骤3：设计递归函数
定义递归函数 dfs(node, currentSum)：

• node 是当前遍历到的节点
• currentSum 是到达当前节点时，路径已表示的数值
  函数的任务：

1. 如果 node 为空，直接返回（递归的终止条件之一）。
2. 更新当前数值：currentSum = currentSum * 10 + node.val。
3. 如果当前节点是叶子（node.left 和 node.right 均为空），则将 currentSum 加入总和。
4. 如果不是叶子，继续递归遍历左子树和右子树，传入更新后的 currentSum 值。

步骤4：举例演示
以 root = [1,2,3] 为例：

1. 从根节点1开始，currentSum = 0*10 + 1 = 1。节点1不是叶子，继续搜索左右子节点。
2. 进入左子节点2：currentSum = 1*10 + 2 = 12。节点2是叶子，将12加入总和（总和=12）。
3. 回到节点1，进入右子节点3：currentSum = 1*10 + 3 = 13。节点3是叶子，将13加入总和（总和=12+13=25）。
   最终返回25。

步骤5：代码实现（Python示例）

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def dfs(node, current_sum):
            if not node:
                return
            current_sum = current_sum * 10 + node.val
            if not node.left and not node.right:  # 叶子节点
                self.total_sum += current_sum
                return
            dfs(node.left, current_sum)
            dfs(node.right, current_sum)
        
        self.total_sum = 0
        dfs(root, 0)
        return self.total_sum

复杂度分析

• 时间复杂度：O(N)，其中 N 是节点数，每个节点被访问一次。
• 空间复杂度：O(H)，其中 H 是树的高度，即递归栈的最大深度。最坏情况下（树退化为链表）为 O(N)。

总结
这道题是树结构的深度优先搜索应用，关键在于在递归过程中传递并更新路径数值，并在叶子节点处完成累加。通过这个例子，可以加深对树遍历和路径处理中状态传递的理解。