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

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

题目描述

给定一个仅包含 0-9 的二叉树，每条从根到叶的路径都代表一个数字。例如路径 1 -> 2 -> 3 代表数字 123。请计算所有路径代表的数字之和。

解法思路

这个问题需要我们在遍历过程中'携带'信息。前序遍历（根 - 左 - 右）非常适合这种场景，因为我们需要从根节点开始，逐层向下累加数值。

核心逻辑如下：

1. 状态传递：在递归调用时，将父节点累积的数字传递给子节点。公式为 current_num = parent_num * 10 + current_node_val。
2. 叶子节点处理：当到达叶子节点时，说明找到了一条完整路径，此时返回该路径代表的数字。
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) {
        // 如果是叶子节点，直接返回该节点代表的数字
        if (root->left == nullptr && root->right == nullptr) {
            return root->val;
        }
        
        int leftSum = 0, rightSum = 0;
        
        // 处理左子树
        if (root->left) {
            TreeNode* left = root->left;
            // 更新左子节点值为当前路径累积值
            left->val = root->val * 10 + root->left->val;
            leftSum = sumNumbers(left);
        }
        
        // 处理右子树
        if (root->right) {
            TreeNode* right = root->right;
            // 更新右子节点值为当前路径累积值
            right->val = root->val * 10 + root->right->val;
            rightSum = sumNumbers(right);
        }
        
        return leftSum + rightSum;
    }
};

总结

这两个题目展示了 DFS 在二叉树中的两种典型应用模式：

1. 自底向上聚合：如计算布尔值，先算出子节点结果，再结合当前节点逻辑得出父节点结果。
2. 自顶向下传递：如路径求和，在递归下行时携带并更新状态，到达终点后返回结果。

掌握这两种模式，配合对递归终止条件的精准把握，就能解决大部分二叉树相关的算法问题。