解法一

1、思路

• 分别从树中每一个节点开始往下遍历，递归查找和为sum的路径；

• 存在大量的重复计算，最坏情况的时间复杂度为 $O(N^2)$ ，比如一棵呈直线形状的树；因为需要压栈，最坏情况下空间复杂度为 $O(N)$。

2、代码

class Solution {
private:
    int res = 0;

public:
    void dfs(TreeNode* root, int sum)
    {
        if (root == nullptr) return;

        sum -= root->val;
        if (sum == 0)
        {
            ++ res;
        }

        dfs(root->left, sum);
        dfs(root->right, sum);
        sum += root->val;           //还原当前节点
    }

    int pathSum(TreeNode* root, int sum) {
        if (root == nullptr) return 0;
        dfs(root, sum);             //从当前节点往下遍历查找求和路径

        pathSum(root->left, sum);   //遍历树中每个节点，分别从这些节点开始往下查找求和路径
        pathSum(root->right, sum);

        return res;
    }
};

解法二：前缀和+哈希

1、思路

• 遍历树时计算从根节点到当前节点路径的和，将这个前缀和存入哈希表中，哈希表的键是前缀和，值是该前缀和出现的次数；

• 初始化prefix[0] = 1表示前缀和为0的路径有1条；

• prefix[cur - sum]表示在树中当前节点cur之前找到某个节点pre，使得从pre节点到cur节点的路径和为sum的总条数。

• 时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

2、代码

class Solution {
public:
    int dfs(TreeNode* root, int cur, int sum, unordered_map<int, int>& prefix)
    {
        if (root == nullptr) return 0;

        cur += root->val;

        int res = prefix[cur - sum];                //哈希表中默认值是零值

        prefix[cur] ++ ;                            //当前路径和加1
        res += dfs(root->left, cur, sum, prefix);   //递归累加找到的路径和
        res += dfs(root->right, cur, sum, prefix);
        prefix[cur] -- ;                            //还原

        return res;
    }

    int pathSum(TreeNode* root, int sum) {
        unordered_map<int, int> prefix;
        prefix[0] = 1;

        return dfs(root, 0, sum, prefix);
    }
};