C++ | Prefix sum beats 99%
\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0)
```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\n    int count = 0, target;\n    unordered_map<int, int> seen;\npublic:\n    int pathSum(TreeNode* root, int targetSum) {\n        target = targetSum;\n        _pathSum(root, 0);\n        return count;\n    }\n    void _pathSum(TreeNode* node, int sum) {\n        // EMPTY\n        if(!node) return;\n        // UPDATE\n        sum += node -> val;\n        // Scenario 1 (sum path from root)\n        if(sum == target) count++;\n        // Scenario 2 (sum path from "middle" of tree)\n        if(seen.find(sum - target) != seen.end()) count += seen[sum - target];\n        seen[sum]++;\n        // RECURSE\n        _pathSum(node -> left, sum);\n        _pathSum(node -> right, sum);\n        // UNDO (backtrack)\n        seen[sum]--;\n    }\n};\n```
['Backtracking', 'Depth-First Search', 'Recursion', 'C', 'C++']