August 08, 2019

437. Path Sum III

Sol 1. Recursion - Non-optimal Solution

Time = O(n^2), Space = O(n)

写法1. Recursive

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int numOfPath = 0;
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        pathSumHelper(root, sum);
        pathSum(root.left, sum); //can start from every node
        pathSum(root.right, sum);
        return numOfPath;
    }
    
    private void pathSumHelper(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        if (root.val == sum) { //can end from every node
            numOfPath += 1;
        }
        pathSumHelper(root.left, sum - root.val);
        pathSumHelper(root.right, sum - root.val);
    }
}

写法2. Recursive - divide and conquer

/**
 * 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;
        }
        int curPath = getPath(root, sum);
        int childPath = pathSum(root.left, sum) + pathSum(root.right, sum);
        return curPath + childPath;
    }
    
    private int getPath(TreeNode root, int sum) {
        int res = 0;
        if (root == null) {
            return res;
        }
        if (root.val == sum) {
            res ++;
        }
        res += getPath(root.left, sum - root.val);
        res += getPath(root.right, sum - root.val);
        return res;
    }
}

Sol 2. Prefix Sum - optimal solution

This problem is tree version of 560. Subarray Sum Equals K

Use a map to store: “prefix sum -> how many times was it seen so far”.

Time = O(n), Space = O(n)

写法1. Recursive

/**
 * 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 {
    int numOfPath = 0;
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        pathSumHelper(root, 0, map, sum);
        return numOfPath;
    }
    
    private void pathSumHelper(TreeNode root, int curSum, Map<Integer, Integer> map, int sum) {
        if (root == null) {
            return;
        }
        curSum += root.val;
        if (map.containsKey(curSum - sum)) {
            numOfPath += map.get(curSum - sum);
        }
        map.put(curSum, map.getOrDefault(curSum, 0) + 1);
        pathSumHelper(root.left, curSum, map, sum);
        pathSumHelper(root.right, curSum, map, sum);
        map.put(curSum, map.getOrDefault(curSum, 0) - 1); // backtrack
    }
}

写法2. Recursive - divide and conquer

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int res = getPath(root, 0, map, sum);
        return res;
    }
    
    private int getPath(TreeNode root, int curSum, Map<Integer, Integer> map, int sum) {
        int res = 0;
        if (root == null) {
            return res;
        }
        curSum += root.val;
        
        if (map.containsKey(curSum - sum)) {
            res += map.get(curSum - sum);
        }
        map.put(curSum, map.getOrDefault(curSum, 0) + 1);
        res += getPath(root.left, curSum, map, sum);
        res += getPath(root.right, curSum, map, sum);
        map.put(curSum, map.getOrDefault(curSum, 0) - 1); // backtrack
        return res;
    }
}