二叉树 DFS 实战：计算布尔值及根到叶节点数字之和

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

题目链接

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

题目描述

给定一个二叉树，每个节点存储一个 0-9 的数字。每条从根到叶的路径可表示一个数字，求所有路径数字的总和。

题目示例

解法思路

此题适合使用前序遍历（根 -> 左 -> 右），因为子节点的状态依赖于父节点传递过来的累积值。

1. 状态传递：在递归过程中，将父节点的数值乘以 10 加上当前节点的值，形成新的路径数。
2. 回溯汇总：当到达叶子节点时，不再向下传递，而是将该路径形成的数字返回给上一层。
3. 累加求和：每一层递归将左右子树返回的结果相加，最终根节点即为总和。

同样，为了演示递归中的状态携带，代码中展示了通过修改子节点 val 来传递中间结果的方式，实际开发中建议通过函数参数传递 currentSum 以保持输入树不变。

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 的特性。

第一题侧重于自底向上的逻辑聚合，利用递归天然的回溯机制，在返回途中完成布尔运算。第二题侧重于自上而下的信息传递，在递归调用前更新状态，在返回时汇总结果。

在实际工程中，如果不需要复用原树结构，上述利用节点字段暂存状态的写法可以节省部分栈空间；但为了代码的可读性和安全性，推荐显式传递累积变量作为参数。掌握这两种模式，基本能覆盖大部分树形递归问题。