437 路径总和iii

class Solution {
public:
    int pathNumber = 0;
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        //尝试用二叉树的每一个节点为搜索起点，判断路径和是否等于sum
        dfs(root, sum);
        pathSum(root->left, sum);
        pathSum(root->right, sum);
        return pathNumber;
    }
    void dfs(TreeNode* root, int sum) {
        if (!root) 
            return;
        sum -= root->val;
        if (!sum) 
            ++pathNumber;
        dfs(root->left, sum);
        dfs(root->right, sum);
    }
};

class Solution {
public:
    map<int, int>mp;
    int count = 0;
    void dfs(TreeNode* root, int ans,int sum)
    {
        if (root == NULL)
            return;
        ans = ans + root->val;
        
        count += mp[ans - sum];
        mp[ans]++;
        dfs(root->left, ans,sum);
        dfs(root->right, ans,sum);
        //回溯的时候要把标记过的一些点清除掉，否则会重复计算
        mp[ans]--;
        return;

    }
    int pathSum(TreeNode* root, int sum) {
        mp[0] = 1;
        dfs(root, 0, sum);
        return count;
    }
};