Path sum III

Path Sum III - LeetCodeLeetCode

It's a good example of double DFS in the brute force implementation

class Solution {
  public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        return 
        dfs(root, targetSum, 0) 
        + pathSum(root.left, targetSum) 
        + pathSum(root.right, targetSum);
    }

    private int dfs(TreeNode node, int targetSum, long sum) {
        if (node == null) {
            return 0;
        }
        sum += node.val;
        int count = sum == targetSum ? 1 : 0;
        count += dfs(node.left, targetSum, sum);
        count += dfs(node.right, targetSum, sum);
        return count;
    }
}

Where we can use pre-sum to change it to one layer DFS, to optimize the algorithm from O(n2) to O(n)

class Solution {
  int count = 0;
  public int pathSum(TreeNode root, int targetSum) {
         Map<Long, Integer> sumCounterMap = new HashMap<>();
        sumCounterMap.put(0L, 1);
        dfs(root, targetSum, 0L, sumCounterMap);
        return count;
    }

    private void dfs(TreeNode node, int targetSum, long curSum, 
        Map<Long, Integer> sumCounterMap) {
        if (node == null) {
            return;
        }
        curSum += node.val;
        if (sumCounterMap.containsKey(curSum-targetSum)) {
            count += sumCounterMap.get(curSum-targetSum);
        }
        sumCounterMap.put(curSum, sumCounterMap.getOrDefault(curSum, 0) + 1);
        dfs(node.left, targetSum, curSum, sumCounterMap);
        dfs(node.right, targetSum, curSum, sumCounterMap);
        sumCounterMap.put(curSum, sumCounterMap.get(curSum) - 1);
    }
}