Path Sum I

Root-to-leaf Path + return true or false

Mistakes

the value of node might be negative integers, so don't need to check whether current value is smaller than sum

• [-2, null, -3] sum = -5

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null && sum == root.val) {
            return true;
        }

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

Path Sum II

Root-to-leaf Path + return paths

Mistakes

check the condition on leaf node, instead of going down to null node

• otherwise, the same path will be added twice to the result

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();

        pathSumHelper(root, sum, new ArrayList<Integer>(), res);

        return res;
    }

    public void pathSumHelper(TreeNode node, int sum, List<Integer> list, List<List<Integer>> res) {
        if (node == null) return;

        list.add(node.val);
        sum -= node.val;

        if (node.left == null && node.right == null && sum == 0) {
            res.add(new ArrayList<Integer>(list));
        }

        pathSumHelper(node.left, sum, list, res);
        pathSumHelper(node.right, sum, list, res);

        list.remove(list.size() - 1);
    }
}

Path Sum III

Any paths that go downwards + return total number of paths

Method I - Divide and Conquer - O(n^2)

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

    private int findPath(TreeNode root, int target) {
        if (root == null) {
            return 0;
        }

        int result = findPath(root.left, target - root.val) + findPath(root.right, target - root.val);

        if (target == root.val) result++;

        return result;
    }
}

Method II - Prefix Sum + Hash Table- O(n)

Prefix Sum => whether this is a subarray that add up to a target value

• whether there is a prefix sum that equals to (current sum - target)

Don't forget to remove the current node

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> prefixSum = new HashMap<>();
        prefixSum.put(0, 1);
        int result = dfsHelper(prefixSum, root, sum, 0);

        return result;
    }

    private int dfsHelper(Map<Integer, Integer> prefixSum, TreeNode root, int target, int sum) {
        if (root == null) return 0;

        sum += root.val;
        int result = prefixSum.getOrDefault(sum - target, 0);

        prefixSum.put(sum, prefixSum.getOrDefault(sum, 0) + 1);

        result += dfsHelper(prefixSum, root.left, target, sum);
        result += dfsHelper(prefixSum, root.right, target, sum);
        prefixSum.put(sum, prefixSum.get(sum)-1);

        return result;
    }
}

Path Sum IV

Any paths that go downwards or upwards + return paths