二叉树 DFS 实战：计算布尔值与路径数字和

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

题目链接

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

题目描述

题目示例

解法：DFS（前序遍历）

算法思路

前序遍历（根 -> 左 -> 右）非常适合处理这种'状态依赖父节点'的问题。我们需要将父节点累积的数字传递给子节点，并在到达叶子节点时将完整数字汇总。

具体步骤如下：

1. 状态传递：在递归调用时，将当前路径形成的数值乘以 10 加上当前节点值，作为新的状态传给下一层。
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 在二叉树中的典型应用。第一题侧重于自底向上的逻辑归约，第二题侧重于自上而下的状态传递。掌握这两种模式，就能应对大部分涉及路径统计或树形计算的题目。