问题：如何计算二叉树中从根节点到所有叶子节点路径的数字之和？

Question

在二叉树中，如何高效计算从根节点到所有叶子节点路径所构成的数字之和？例如，每条从根到叶的路径可以转换为一个数字，如路径 1→2→3 表示数字 123，如何将所有路径数字相加？该问题常用于考察二叉树的遍历策略与递归或回溯算法的实现。

Answer 1

在二叉树中高效计算从根节点到所有叶子节点路径构成的数字之和

1. 问题描述与初步理解

在二叉树中，每条从根节点到叶子节点的路径可以被看作是一个数字。例如路径 1 → 2 → 3 可以表示为数字 123。我们的目标是将所有这样的路径所代表的数字相加。

该问题常用于考察对二叉树遍历的理解，以及对递归、回溯等算法的掌握程度。

2. 基本思路：深度优先遍历（DFS）

由于我们需要访问每条从根到叶的路径，因此可以采用深度优先遍历（DFS）策略，递归地访问每个节点，并在到达叶子节点时计算路径所构成的数字。

• 递归函数中维护当前路径的数值
• 每访问一个节点，当前数值乘以10并加上当前节点的值
• 当遇到叶子节点时，将当前数值加入总和

3. 递归实现示例（Python）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sum_numbers(root):
    def dfs(node, current_sum):
        if not node:
            return 0
        current_sum = current_sum * 10 + node.val
        if not node.left and not node.right:
            return current_sum
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)
    return dfs(root, 0)
    

4. 算法流程图（mermaid）

graph TD
            A[开始] --> B{当前节点是否为空?}
            B -->|是| C[返回0]
            B -->|否| D[更新当前路径值]
            D --> E{是否为叶子节点?}
            E -->|是| F[返回当前路径值]
            E -->|否| G[递归左子树]
            E -->|否| H[递归右子树]
            G --> I[合并结果]
            H --> I
            I --> J[返回总和]

5. 时间与空间复杂度分析

维度	复杂度
时间复杂度	O(n)，其中n为节点数，每个节点仅访问一次
空间复杂度	O(h)，h为树的高度，递归栈的深度

6. 拓展思路：非递归实现（迭代法）

除了递归方式，也可以使用栈来模拟递归过程，实现非递归版本的DFS算法。

核心思想：使用栈保存当前节点与当前路径值，每次出栈处理节点并更新路径值。

def sum_numbers_iterative(root):
    if not root:
        return 0
    stack = [(root, root.val)]
    total_sum = 0
    while stack:
        node, current_sum = stack.pop()
        if not node.left and not node.right:
            total_sum += current_sum
        if node.right:
            stack.append((node.right, current_sum * 10 + node.right.val))
        if node.left:
            stack.append((node.left, current_sum * 10 + node.left.val))
    return total_sum
    

7. 实际应用与变体问题

此问题不仅适用于标准的二叉树结构，还可拓展至：

• N叉树中路径和的计算
• 路径中数字构造为二进制、十六进制等格式
• 路径和等于某个目标值的判断