二叉树深度优先遍历实战：计算布尔值与路径数字和

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

题目链接

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

题目描述

给定一个二叉树，其中每个节点存储一个 0-9 的数字。从根节点到叶节点的路径可以组成一个数字（例如路径 1->2->3 代表数字 123）。请计算所有从根到叶路径组成的数字之和。

题目示例

解法 (DFS-前序遍历)

算法思路

前序遍历（根 -> 左 -> 右）非常适合这类'状态依赖父节点'的问题。我们需要将当前路径累积的数字传递给子节点。

1. 状态传递：在递归过程中，维护一个当前路径形成的数值 currentSum。每进入下一层，更新为 currentSum * 10 + node.val。
2. 叶子判断：当到达叶子节点时，说明找到了一条完整路径，将此时的 currentSum 加入总和。
3. 回溯累加：递归返回时，将左右子树计算出的路径和相加并返回给上一层。

C++ 算法代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        // 辅助函数，携带当前路径数值
        return dfs(root, 0);
    }

private:
    int dfs(TreeNode* node, int currentSum) {
        if (!node) return 0;
        
        // 更新当前路径数值
        currentSum = currentSum * 10 + node->val;
        
        // 如果是叶子节点，返回当前累积值
        if (!node->left && !node->right) {
            return currentSum;
        }
        
        // 递归左右子树并累加结果
        return dfs(node->left, currentSum) + dfs(node->right, currentSum);
    }
};

注：上述代码为了清晰展示逻辑，使用了辅助函数 dfs 来传递状态。原输入中的实现尝试通过修改节点值来传递状态，这在某些特定约束下可行，但使用额外参数通常更符合函数式编程习惯且不易产生副作用。

算法总结及流程解析