437. Path Sum III

Problem Statement

Pattern:

---

Solution

public int pre(TreeNode root, int target, HashMap<Integer, Integer> map, int currSum) {
	if(root == null) return 0;
	
	currSum += root.val;                                // update currSum
	int count = map.getOrDefault(currSum-target, 0);    // update count of currSum-target
	
	map.put(currSum, map.getOrDefault(currSum, 0) + 1); // increment count of currSum
	count +=                                            // get counts from left, right subtree
		pre(root.left, target, map, currSum) + 
		pre(root.right, target, map, currSum);
 
	map.put(currSum, map.get(currSum) - 1);             // decrement count of currSum
	return count;                                       // return count of currSum-target
}
 
public int pathSum(TreeNode root, int targetSum) {
	HashMap<Integer, Integer> map = new HashMap<>();
	map.put(0, 1); // root condition
	return pre(root, targetSum, map, 0);   
}

Notes

• bascially every path you travel, create a prefix sum array, and count the number of times currSum-target has ocurred in the array
• to maintain the array, for every path, increment the count of currSum when traversing a node, and decrement it when returning from the node