给定一个二叉树，它的每个结点都存放着一个整数值。
    找出路径和等于给定数值的路径总数。
    路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
    二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
    示例：

    1. root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
    2.       10
    3.      /  \
    4.     5   -3
    5.    / \    \
    6.   3   2   11
    7.  / \   \
    8. 3  -2   1
    9. 返回 3。和等于 8 的路径有:
    10. 1.  5 -> 3
    11. 2.  5 -> 2 -> 1
    12. 3.  -3 -> 11
    /**
 * 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:
    unordered_map<int, int> m{{0,1}};
    int diff, res = 0;
public:
    void dfs(TreeNode* root, int cur_sum)
    {
        if (root == nullptr) return;
        if(m.count(cur_sum - diff))
            res += m[cur_sum - diff];
        m[cur_sum] ++;
        if(root->left)  dfs(root->left, cur_sum + root->left->val);
        if(root->right) dfs(root->right, cur_sum + root->right->val);
        m[cur_sum] --;
    }
    int pathSum(TreeNode* root, int sum) {
        if(root == nullptr) return 0;
        diff = sum;
        dfs(root, root->val);
        return res;
    }
};