C++ || O(n) || 8ms || Prefix Sum solution with explanation || 99.07% faster
For each node, we will calculate cumulative sum of node val and add it to the map. If the value of sum is greater than target sum, that means we have extra (sum
For each node, we will calculate cumulative sum of node val and add it to the map. If the value of sum is greater than target sum, that means we have extra (sum - target) value to our sum. Now, we will check our hashmap if (sum-target) extra value is availble to our map or not. If it\'s available that means we can remove some nodes from top to get target sum.\n\n**Time Complexity**: O(n)\n**Space Complexity**: O(n)\n\n```\nclass Solution {\n    unordered_map<long, int> hashMap;\n    int count;\n    int target;\n    void find(TreeNode* root, long sum) {\n        if (root == 0) return;\n        sum += root->val;\n        int prefixSum = sum - target;\n        if (hashMap.count(prefixSum)) {\n            count += hashMap[prefixSum];\n        }\n        hashMap[sum]++;\n        find(root->left, sum);\n        find(root->right, sum);\n        hashMap[sum]--;\n    }\npublic:\n    int pathSum(TreeNode* root, int targetSum) {\n        count = 0;\n        target = targetSum;\n        hashMap[0] = 1;\n        find(root, 0);\n        return count;\n    }\n};\n```
['Hash Table', 'C', 'Prefix Sum', 'C++']