C++ solution with prefix sum stored in hash table
The idea is simple: along the path, record all prefix sums in a hash table. For current prefix sum x, check if (x - target) appears in the hash table. \n\nclass
The idea is simple: along the path, record all prefix sums in a hash table. For current prefix sum x, check if (x - target) appears in the hash table. \n```\nclass Solution {\npublic:\n    int pathSum(TreeNode* root, int sum) {\n        unordered_map<int, int> m;\n        m[0]++;\n        \n        int total = 0;\n        helper(root, 0, sum, total, m);\n        return total;\n    }\n    \n    void helper(TreeNode *p, int cur, int sum, int &total, unordered_map<int, int> &m) {\n        if (!p) return;\n        \n        cur += p->val;\n        if (m.find(cur - sum) != m.end()) total += m[cur - sum];\n        m[cur]++;\n        \n        helper(p->left, cur, sum, total, m);\n        helper(p->right, cur, sum, total, m);\n        \n        m[cur]--;\n    }\n};\n```
[]