Easy Solution using Java | DFS | Map
Simple Solution:\n\nStart helper method from all the nodes and compute the total count.\n\n\nclass Solution {\n    public int pathSum(TreeNode root, int targetS
**Simple Solution:**\n\nStart helper method from all the nodes and compute the total count.\n\n```\nclass Solution {\n    public int pathSum(TreeNode root, int targetSum) {\n        if(root == null)\n            return 0;\n        \n        return pathSum(root.left, targetSum) + pathSum(root.right, targetSum) + helper(root, 0, targetSum);\n    }\n    \n    int helper(TreeNode root, int current, int target) {\n        if(root == null)\n            return 0;\n        \n        current += root.val;\n        \n        return (current == target ? 1 : 0) + helper(root.left, current, target) + helper(root.right, current, target);\n    }\n}\n```\n\nThis approach is time consuming since we will be visiting each non-root node more than once. We can optimize this using path sum in each node and map.\n\n**Optimized solution**\n![image](https://assets.leetcode.com/users/images/2757c4b0-67c2-4bad-9330-cc0774845458_1634437241.3073082.jpeg)\n\n\nFrom the above tree, lets take a path\n\n10 -> 5 -> 2 -> 1, target = 8\n\nmap -> [0, 1], [10, 1], [15, 1], [17, 1]\n\nwhen we reach element 1, current path sum is 18. but our target is 8. we can check in the map if we have sum 10(18-8). if so we can add it the count.\n\n```\nclass Solution {\n    public int pathSum(TreeNode root, int targetSum) {\n        if(root == null)\n            return 0;\n        \n        Map<Integer, Integer> map = new HashMap<>();\n        map.put(0, 1);\n        return helper(root, 0, targetSum, map);\n    }\n    \n    public int helper(TreeNode root, int current, int target, Map<Integer, Integer> map) {\n        if(root == null)\n            return 0;\n        \n        current += root.val;\n        int count = 0;\n        \n        count += map.getOrDefault(current - target, 0);\n        map.put(current, map.getOrDefault(current, 0) + 1);\n        \n        count += helper(root.left, current, target, map);\n        count += helper(root.right, current, target, map);\n        \n        map.put(current, map.get(current) - 1);\n        return count;\n    }\n}\n```\n\nWhy do we need to use map? Why can\'t we use set and add 1 to the count?\n```\n      0\n 1       1\n \n\ntarget = 1\n \nfor this example, result is 4\n\n1) 1\n2) 1\n3) 0 -> 1\n4) 0 -> 1\n```\nif we are not keeping the count, then result will be incorrect.\n
['Depth-First Search', 'Java']