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

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

步骤 1：定义问题性质与输入输出条件

问题性质
这是一个二叉树的遍历与数值计算问题，需要从根到叶节点的所有路径，组合成数字并计算总和。

输入条件

• 一个二叉树的根节点 root，树中每个节点的值为 0-9。
• 树节点数量范围 [1, 1000]。
• 树深度不超过 10。

输出条件

• 从根到所有叶节点路径形成的数字之和。

限制与边界条件

• 空树（边界条件）：若 root 为 null，输出为 0。
• 单节点树：路径仅包含根节点值。
• 树结构不固定，需要适应各种形态的二叉树。

步骤 2：问题分解与最佳算法设计思路

问题分解

1. 从根到叶节点遍历
   • 每条从根到叶的路径需要进行一次深度优先遍历（DFS）。
2. 路径生成数字
   • 沿着遍历路径，累积形成当前数字。
3. 累积总和
   • 在叶节点完成时，将路径生成的数字累加到结果中。

算法设计思路

• 使用 深度优先搜索（DFS） 来遍历树，每次从根节点递归到叶节点。
• 通过递归参数记录当前路径所形成的数字。
• 遍历结束时，返回所有数字的累加值。

复杂度分析

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

步骤 3：C++代码实现

代码解释

1. 定义 dfs 函数

   • dfs 接受两个参数：
     • node: 当前二叉树节点。
     • currentSum: 当前路径累积的数值。
   • 若节点为空，返回0。
   • 若节点为叶节点，直接返回路径生成的数字。

2. 在 sumNumbers 中调用 dfs

   • 从根节点开始递归，初始路径总和为0。
   • 返回整个树从根到叶节点的路径数字之和。

3. 递归逻辑

   • 递归地计算左子树和右子树的路径数字之和，将结果相加。

步骤 4：问题启发与优化

算法启发

1. 递归思路简洁：通过递归设计，避免了显式路径存储，仅利用参数传递路径信息。
2. 高效性：通过深度优先搜索，避免不必要的节点访问，实现时间效率的优化。

优化思路

• 如果树非常深（>10），可考虑使用迭代（栈模拟）以减少递归调用栈消耗。
• 若节点值更复杂（如大整数），可以利用字符串代替数字运算。

步骤 5：实际生活中的应用

应用场景

1. 路径计算与编码
   • 在导航系统中，将路径节点值作为编码，每条路径生成唯一标识符。
2. 决策树路径总和
   • 在金融风险评估中，计算决策树中不同路径的总风险值。

实际案例：物流配送路径标识

• 场景: 在物流行业，二叉树表示配送路线，节点值为配送点编号，从根到叶形成配送路径。
• 实现方法:
  使用上述算法生成所有配送路径的唯一编码并计算总数，用于路径优化或统计分析。