437.Path Sum III

Solution 1 - DFS - O

Typical recursive DFS

Space: O(n) due to recursion.

Time: O(n^2) in worst case (no branching); O(nlogn) in best case (balanced tree).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null){
            return 0;
        }
        return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    public int pathSumFrom(TreeNode root, int sum){
        if(root == null){
            return 0;
        }
        else{
            int cnt = 0;
            if(root.val == sum){
                cnt += 1;
            }
            cnt += pathSumFrom(root.left, sum - root.val);
            cnt += pathSumFrom(root.right, sum - root.val);
            return cnt;
        }
    }
}

Solution 2: prefix Sum

 public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);  //Default sum = 0 has one count
        return backtrack(root, 0, sum, map); 
    }
    //BackTrack one pass
    public int backtrack(TreeNode root, int sum, int target, Map<Integer, Integer> map){
        if(root == null)
            return 0;
        sum += root.val;
        int res = map.getOrDefault(sum - target, 0);    //See if there is a subarray sum equals to target
        map.put(sum, map.getOrDefault(sum, 0)+1);
        //Extend to left and right child
        res += backtrack(root.left, sum, target, map) + backtrack(root.right, sum, target, map);
        map.put(sum, map.get(sum)-1);   //Remove the current node so it wont affect other path
        return res;
    }