C++ | Explained + Clean code | Same problem as Leetcode #560 | O(n); O(n)
If you notice that this problem is the same as the \'Subarray Sum Equals K\' one, then the solution becomes trivial. Instead of searching for subarrays with the
If you notice that this problem is the same as the \'Subarray Sum Equals K\' one, then the solution becomes trivial. Instead of searching for subarrays with the given sum in an array, we search for subpaths in our tree.\nIf you, however, either don\'t know the \'Subarray Sum Equals K\' problem, or you don\'t observe the trick, read my explanation. \n```\nclass Solution {\npublic:\n    int nr = 0;                                               // This is our answer\n    void dfs(TreeNode *node, int s, unordered_map <int, int> di, int sum) {\n        if (!node) return;                                    // If we don\'t have any nodes in our path, we leave the recursion\n        s += node->val;                                       // Every time we have a node with a value, we add its value to our \'s\'\n        nr += di[s - sum];                                    // Our map maintains how many times we\'ve already got a specific sum (left pointer). \'s\' is the right pointer. If we\'ve got a left pointer with the value \'s - sum\', then we have a subpath with the sum \'s - (s - sum)\' = \'sum\', which is what we need\n        di[s] ++;                                             // Increase the number of left pointers which have the sum \'s\'\n        dfs(node->left , s, di, sum);                         // Continue our path to the left\n        dfs(node->right, s, di, sum);                         // Continue our path to the right\n    }\n    int pathSum(TreeNode* root, int sum) {\n        dfs(root, 0, unordered_map <int, int> {{0, 1}}, sum); // We run a dfs from the root; See \'P.s.\' for the \'unordered_map <int, int> {{0, 1}}\' part\n        return nr;                                            // return answer\n    }\n};\n```\nP.s. Let us take an example with a tree which has only one node with value equal to our target sum. Its clear that the answer should be 1, where we take our node to our path. The pair {0, 1} from our map creates a left pointer for such cases. In other words, we create a dummy node before our root with a value 0. You can check that \'dfs(new TreeNode(0, root, NULL), 0, unordered_map <int, int> {}, sum);\' also works.
[]