Simple Solution in O(N) Time Complexity in C++ using Pre-fix Sum and Hashmap
Method : Prefix Sum in a Hasmap\nTime Complexity: O(N)\nSpace Complexity: O(N)\nExplanation:\nA prefix sum can be used to get continous sums between 2 indices i
Method : Prefix Sum in a Hasmap\nTime Complexity: O(N)\nSpace Complexity: O(N)\nExplanation:\nA prefix sum can be used to get continous sums between 2 indices in an array in O(1) time (given we know the indices). A similar concept can be used here to get continous sums between nodes.\n1. We maintain curr_sum, which is the running sum of the nodes encountered from the root(actual root) to the current node.\n2. We keep storing this sum in a Hashmap Times, representing the number of times we have encountered a branch with sum curr_sum.\n3. Then we check if we have a branch that if we subtract from our current branch that will give us the sum "*sum*". This can be done by checking times[curr_sum - sum] and adding that count to *count* variable.\n4. After that we can solve for the left and right nodes.\n5. After returning from the subtrees, we must decrement the times[curr_sum]. This step is the **backtracking** step. \n5. We must initialize the hashmap times[0] = 1, as if we encounter a branch that originates from root and has sum == *sum*, then count should be increased by 1.\n\nC++ code is as follows\n```\nclass Solution {\npublic:\n    unordered_map<int, int> times;\n    int count = 0;\n    void solve(TreeNode* root, int curr_sum, int sum){\n        if(root == NULL) return;\n        curr_sum += root->val;\n        count += times[curr_sum - sum];\n        times[curr_sum]++;\n        solve(root->left, curr_sum, sum);\n        solve(root->right, curr_sum, sum);\n        times[curr_sum]--;\n        return;\n    }\n    \n    int pathSum(TreeNode* root, int sum) {\n        times[0] = 1;\n        solve(root, 0, sum);\n        return count;\n    }\n};\n```
['Tree', 'C', 'Prefix Sum', 'Python', 'C++', 'Java']