C++ / Python Simple and Easy DFS Solutions, Faster than 99%
Idea:\nWe keep the prefix sums in a hashmap and then in each stage we can check if we have prev_sum - target, which means that we got a path sum equals target.\
**Idea:**\nWe keep the prefix sums in a hashmap and then in each stage we can check if we have `prev_sum - target`, which means that we got a path sum equals `target`.\n\n**C++:**\n```\nclass Solution {\npublic:\n    void dfs(TreeNode* root, int target, int prev_sum) {\n        if (!root) return;\n        prev_sum += root->val;\n        \n        res += prefix[prev_sum - target];\n        \n        prefix[prev_sum]++;\n        \n        dfs(root->left, target, prev_sum);\n        dfs(root->right, target, prev_sum);\n        \n        prefix[prev_sum]--;\n    }\n    \n    int pathSum(TreeNode* root, int targetSum) {\n        prefix[0]++;\n        dfs(root, targetSum, 0);\n        return res;\n    }\n    \nprivate:\n    unordered_map<int, int> prefix;\n    int res = 0;\n};\n```\n****\n**Python:**\n```\nclass Solution:\n    def pathSum(self, root: TreeNode, sum: int) -> int:\n        prefix = defaultdict(int)\n        prefix[0] = 1\n        self.res = 0\n        \n        def dfs(root:TreeNode, target:int, prev_sum:int):\n            if not root:\n                return\n            \n            prev_sum += root.val\n            self.res += prefix[prev_sum - target]\n            prefix[prev_sum] += 1\n            \n            dfs(root.left, target, prev_sum)\n            dfs(root.right, target, prev_sum)\n            \n            prefix[prev_sum] -= 1\n            \n        dfs(root, sum, 0)\n        return self.res\n```\n**Like it? please upvote!**
['C', 'Python']