前面几个路径搜素题目的思路和解法已经忘干净了。这道题目真的有点不知道如何处理。

DFS

官方解答 我们首先想到的解法是穷举所有的可能，我们访问每一个节点 node，检测以 node 为起始节点且向下延深的路径有多少种。我们递归遍历每一个节点的所有可能的路径，然后将这些路径数目加起来即为返回结果。

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }
private:
    int res = 0;
    void dfs(TreeNode* root, int targetSum) {
        if (!root) return;
        res += rootSum(root, targetSum);
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);
    }

    int rootSum(TreeNode* root, long targetSum) {
        if (!root) return 0;
        int cnt = 0;
        if (root->val == targetSum) {
            cnt++;
        }
        cnt += rootSum(root->left, targetSum - root->val);
        cnt += rootSum(root->right, targetSum - root->val);
        return cnt;
    }
};

前缀和

https://www.acwing.com/video/1839/

大师，我悟了

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        cnt[0] = 1;
        dfs(root, targetSum, 0);
        return res;
    }
private:
    unordered_map<long, int> cnt;
    int res = 0;
    void dfs(TreeNode* root, int targetSum, long preSum) {
        if (!root) return;
        preSum += root->val;
        res += cnt[preSum - targetSum];
        cnt[preSum] ++;
        dfs(root->left, targetSum, preSum);
        dfs(root->right, targetSum, preSum);
        cnt[preSum] --;
    }
};

[560. 和为 K 的子数组](https://qiekn.notion.site/560-K-12fb23e6df514ba98eeec0940df0611e)