Beats 100.00%of users with Java | Easy DFS Code O(n) Tc & with Explanation
Intuition\nThe intuition behind this code is to use a hash table to keep track of the prefix sums that we have seen so far during the traversal of the tree. For
# Intuition\nThe intuition behind this code is to use a hash table to keep track of the prefix sums that we have seen so far during the traversal of the tree. For each node, we check if the hash table contains a sum equal to (prefixSum - targetSum). If it does, then we know that there exists a path from the root node to the current node with a sum equal to targetSum.\n\n\n# Approach\n* #### Initialize a hash table to store the prefix sums that we have seen so far during the traversal of the tree.\n\n* #### Initialize a counter variable to keep track of the number of paths from the root node to the current node with a sum equal to targetSum.\n* #### Perform a recursive traversal of the tree. For each node:\n* Update the prefix sum by adding the value of the current node.\n* Check if the hash table contains a sum equal to (prefixSum - targetSum). *If it does, then increment the counter variable.\n\n* If the prefix sum is equal to targetSum, then increment the counter variable.\n* Update the hash table to store the current prefix sum and its count.\n* Recursively traverse the left and right subtrees of the current node.\n* Backtrack by removing the current prefix sum and its count from the hash table.\n# Complexity\n- Time complexity:\nThe time complexity of this code is O(n), where n is the number of nodes in the tree. This is because we need to visit each node in the tree once.\n\n\n- Space complexity:\nThe space complexity of this code is O(n), where n is the number of nodes in the tree. This is because we need to store the prefix sums in the hash table.\n\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    // Map for keeping track of (PrefixSum, timesPrefixSumSeen) during traversal\n    Map<Long, Integer> hmap;\n    int count;\n\n    public int pathSum(TreeNode root, int targetSum) {\n        hmap = new HashMap<>();\n        count = 0;\n\n        dfs(root, 0, targetSum);\n\n        return count;\n    }\n\n    private void dfs(TreeNode root, long prefixSum, int targetSum) {\n        // base case\n        if (root == null) return;\n\n        \n        prefixSum += root.val;\n        \n        // If map contains a sum equal to (prefixSum - targetSum), we need to increment count that many times\n        if (hmap.containsKey(prefixSum-targetSum)) {\n            count += hmap.get(prefixSum-targetSum);\n        } \n        \n        // There can be cases when the prefixSum is directly equal to targetSum, we need to increment count\n        if (targetSum == prefixSum) {\n            count++;\n        }\n\n        // Update the prefixSum till current node and it\'s count\n        hmap.put(prefixSum, hmap.getOrDefault(prefixSum, 0) + 1);\n\n        // Recurse\n        dfs(root.left, prefixSum, targetSum);\n        dfs(root.right, prefixSum, targetSum);\n\n        // Backtrack\n        hmap.put(prefixSum, hmap.get(prefixSum) - 1);\n        \n    }\n}\n```
['Java']