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

注意：原解法中有修改树节点值的写法，虽然能跑通，但为了保持树的原始结构不被破坏，建议将返回值存储在局部变量中，如上方代码所示。

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

题目来源： LeetCode 129

解题思路

这道题适合使用前序遍历。因为从根节点到叶节点的路径构成了一个多位数，我们需要把父节点的数值传递下去，并累加当前位的值。

具体步骤如下：

1. 状态传递：在递归调用时，将当前累积的数字 currentSum 传递给下一层。
2. 更新数值：每进入一层，新的累积值等于 currentSum * 10 + 当前节点值。
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 在树形结构中的两种典型应用：

1. 自底向上：通过递归返回值处理子问题，适用于需要聚合子节点信息的场景（如布尔树求值）。
2. 状态传递：通过递归参数维护路径状态，适用于需要记录遍历路径信息的场景（如路径数字求和）。

掌握这两种模式，基本就能应对大部分二叉树的递归问题了。