使用深度优先搜索 DFS 来做
我提供的代码使用的是 深度优先搜索（DFS，Depth-First Search） 算法。以下是具体的算法思想和实现步骤的解释：

---

算法思想

1. 树的路径代表数字：

   • 树中每条从根节点到叶子节点的路径可以看作一个整数。例如路径 1 -> 2 -> 3 表示数字 123。这个数字的计算方式是将路径上每个节点的值按照十进制规则累加。

2. 递归计算路径值：

   • 遍历树时，将当前节点的值加到路径数值中，更新为当前路径的数值 currentSum，公式为：

     currentSum = currentSum * 10 + node.val
     

     每深入一层，就将路径数字向左移一位并加上当前节点的值。

3. 终止条件：叶子节点：

   • 当到达一个叶子节点时，这条路径所表示的数字已经完整，直接返回这个数字。

4. 递归累加左右子树路径的数字：

   • 如果当前节点不是叶子节点，那么递归遍历其左子树和右子树，返回左右子树路径数字的总和。

5. 空节点处理：

   • 如果当前节点为空，返回 0，表示当前路径对最终结果没有贡献。

---

算法流程

1. 从根节点开始，将路径数值初始化为 0。
2. 对树进行深度优先遍历：
   • 更新路径数值：当前路径的数字由上一级路径的值累加当前节点的值。
   • 终止条件：如果当前节点是叶子节点，返回当前路径的值。
   • 递归累加：如果当前节点有子节点，递归调用左右子树，将左右子树的结果累加。
3. 最终返回所有路径数值的总和。

---

伪代码描述

• 递归方法 dfs(node, currentSum)：
  1. 如果当前节点为空，返回 0。
  2. 更新当前路径的数值：currentSum = currentSum * 10 + node.val。
  3. 如果当前节点是叶子节点，直接返回当前路径的数值 currentSum。
  4. 否则，对左右子树分别递归，累加左右子树的路径数值和并返回。

---

复杂度分析

1. 时间复杂度：

   • 每个节点都被访问一次，递归遍历整棵树，因此时间复杂度是 O(N)，其中 N 是树中节点的个数。

2. 空间复杂度：

   • 递归的栈深度取决于树的高度。如果是平衡二叉树，树高为 log(N)，空间复杂度为 O(log(N))。如果是链状结构（退化为链表），最坏情况空间复杂度为 O(N)。

---

例子分析

假设输入如下树：

    1
   / \
  2   3

• 路径从根节点 1 出发，依次到达叶子节点 2 和 3。
• 执行流程：
  1. 初始调用 dfs(1, 0)，将 currentSum 设为 0。
  2. 进入根节点 1，currentSum = 0 * 10 + 1 = 1。
  3. 递归左子树，调用 dfs(2, 1)，更新路径值：currentSum = 1 * 10 + 2 = 12，返回 12。
  4. 递归右子树，调用 dfs(3, 1)，更新路径值：currentSum = 1 * 10 + 3 = 13，返回 13。
  5. 最终返回左右子树的和：12 + 13 = 25。

---

核心思想总结

• 将路径问题抽象为树的递归遍历，通过递归累加路径数值。
• 使用深度优先搜索，可以有效地对每一条路径进行独立计算，最终累加结果。
• 通过递归的参数传递路径值，不需要额外的数据结构记录路径信息，从而节省了内存。

java 实现

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);
    }
}