437. Path Sum III

 一刷 06/2022

Version #1 DFS prefix sum

有一个很重要的知识点就是prefixSum[0] = 0, 这样subarray starts from the beginning of the array才会被算进去

同理这道题里面要提前加上map.put(0, 1) 否则从root开始path就会被忽略

第二个知识点是Map.of生成的map是immutable的，不能用来初始化后面会被更改的map

第三个就是这道题里面map代表的是prefix sum of the tree's paths above current node，在回到上一层的时候要做backtracking

Time O(N)

Space O(N)

Runtime: 4 ms, faster than 86.56% of Java online submissions for Path Sum III.

Memory Usage: 45.6 MB, less than 7.39% of Java online submissions for Path Sum III.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public int pathSum(TreeNode root, int targetSum) {

        // Use a map to keep track of all root to node path sum above current node

        // If there exists key that satisfy key = targetSum - currentSum, then we can add up the count of the answers

        Map<Integer, Integer> sums = new HashMap<>();

        sums.put(0, 1);

        return dfs(root, sums, targetSum, 0);

    }

    

    private int dfs(TreeNode node, Map<Integer, Integer> sums, int targetSum, int pathSum) {

        if (node == null) {

            return 0;

        }

        //   1      // sums (1,1)

        //  / \

        // 2   3    // currSum = 4 

        int currSum = pathSum + node.val;

        int cnt = sums.getOrDefault(currSum - targetSum, 0);

        sums.put(currSum, 1 + sums.getOrDefault(currSum, 0));

        cnt += dfs(node.left, sums, targetSum, currSum);

        cnt += dfs(node.right, sums, targetSum, currSum);

        sums.put(currSum, sums.get(currSum) - 1);

        return cnt;

    }

}