题解 | #牛群特殊路径的数量#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的主要知识点是二叉树的遍历，如何在二叉树中找出满足给定路径和的路径数量。

题目解答方法的文字分析

我们需要计算二叉树中有多少条路径，使得路径上的节点值之和等于给定的值。这里可以使用深度优先搜索（DFS）的方法来遍历二叉树，同时记录路径上的节点值之和。

思路步骤如下：

1. 从根节点开始递归遍历二叉树。
2. 对于每个节点，计算从根节点到当前节点的路径上的节点值之和，然后判断是否等于给定的值sum。
3. 在遍历过程中，使用一个哈希表（或者unordered_map）来存储从根节点到当前节点的路径上的节点值之和以及出现的次数。
4. 对于每个节点，计算当前节点到根节点的路径上的节点值之和，然后判断是否在哈希表中存在sum - current_sum这个键，如果存在，则说明存在一条从当前节点到某个祖先节点的路径，使得路径上的节点值之和等于给定的值。
5. 递归遍历左子树和右子树。

本题解析所用的编程语言

本题解析所用的编程语言是C++。

完整且正确的编程代码

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        unordered_map<int, int> prefix_sum_count; // 前缀和 -> 该前缀和出现的次数
        prefix_sum_count[0] = 1; // 初始化前缀和为0的出现次数
        
        return dfs(root, prefix_sum_count, sum, 0);
    }
    
    // 深度优先搜索函数
    int dfs(TreeNode* node, unordered_map<int, int>& prefix_sum_count, int target_sum, int current_sum) {
        if (!node) {
            return 0;
        }
        
        int paths_count = 0;
        current_sum += node->val; // 更新当前路径和
        
        // 查找是否存在前缀和，使得当前路径和与目标和之差等于sum
        if (prefix_sum_count.find(current_sum - target_sum) != prefix_sum_count.end()) {
            paths_count += prefix_sum_count[current_sum - target_sum];
        }
        
        prefix_sum_count[current_sum]++; // 更新当前前缀和的出现次数
        
        // 递归遍历左子树和右子树
        paths_count += dfs(node->left, prefix_sum_count, target_sum, current_sum);
        paths_count += dfs(node->right, prefix_sum_count, target_sum, current_sum);
        
        prefix_sum_count[current_sum]--; // 回溯，恢复前缀和的出现次数
        
        return paths_count;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！