Java solution using HashMap

  • 0

    easy as long as you remember to use the map to track sums down.
    remember to remove that after call, and make sure to cover the special case that from top to here sum is equal to the target

    public class Solution {
        public int pathSum(TreeNode root, int sum) {
            helper(root, 0, sum);
            return count;
        int count = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        void helper(TreeNode root, int csum, int sum) {
            if(root == null) return;
            csum += root.val;
            if(csum == sum) count++; //this is special condition
            count += map.getOrDefault(csum-sum, 0);  
            map.put(csum, map.getOrDefault(csum, 0) + 1);
            helper(root.left, csum, sum);
            helper(root.right, csum, sum);
            map.put(csum, map.get(csum) - 1);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.