Path Sum III, DFS + Dynamic prefix sum, O(n) time
This problem is similar to finding number of subarrays having s.\nHere we have to find number of paths(defined as from any node to it\'s succesor) having sum s.
This problem is similar to finding number of subarrays having s.\nHere we have to find number of paths(defined as from any node to it\'s succesor) having sum s.\n\nWe can maintain all prefix sums from root node to current node in hashmap while traversing the tree in dfs, and we need to remove the prefix sum accounted by \'node\' when we return as this prefix sum should not exist for other paths.\n\n```\nclass Solution {\npublic:\n    \n    int pathSum(TreeNode* root, int sum) {\n        \n        unordered_map<int, int> map;\n        return dfs(root, 0, sum, map);\n\t}\n    \n    int dfs(TreeNode *node, int root_to_par, int s, unordered_map<int, int> &map) {\n        if(!node)\n            return 0;\n        \n        int root_to_node = root_to_par + node->val;\n        \n        // stores the count of number of paths having sum = s and ending on current node in dfs()\n        int num_paths_ending_on_node = map[root_to_node - s] + (root_to_node == s ? 1 : 0);  \n        \n        map[root_to_node] += 1;\n        \n        int left  =  dfs(node->left,  root_to_node, s, map);\n        int right =  dfs(node->right, root_to_node, s, map);\n        \n        map[root_to_node] -= 1; \n        \n        return num_paths_ending_on_node + left + right;\n    }\n    \n    \n};\n```
[]