Binary Tree Path Sum

Question (LI.376)

Given the root of a binary tree, from all paths from root -> leaf that sum to the target value.

Example

I: {1,2,4,2,3}, 5
O: [[1,2,2],[1,4]]

Can the values be negative? It doesn't matter we need to go down all the way anyway

Approach

D&C will be long to implement because the CEO has the final say on the report but we need to make that a special case. Instead, we can just traverse from the root.

This question is the same as Binary Tree Paths. D&C has a simpler implementation.

D&C

public List<List<Integer>> binaryTreePathSum(TreeNode root, int targetSum) {
    List<List<Integer>> paths = new ArrayList<>();
    // base
    if (root == null) {
        return paths;
    }
    if (root.left == null && root.right == null) {
        if (root.val == targetSum) {
            List<Integer> path = new ArrayList<>();
            path.add(root.val);
            paths.add(path);
        }
        return paths;
    }
    // divide and conquer
    List<List<Integer>> leftPaths = binaryTreePathSum(root.left, targetSum - root.val);
    List<List<Integer>> rightPaths = binaryTreePathSum(root.right, targetSum - root.val);
    // merge
    for (List<Integer> path : leftPaths) {
        path.add(0, root.val);
        paths.add(path);
    }
    for (List<Integer> path : rightPaths) {
        path.add(0, root.val);
        paths.add(path);
    } 
    return paths;
}

Traversal

public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
    List<List<Integer>> paths = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    traverseHelper(root, target, paths, path);
    return paths;
}

// 2 cases leaf or incomplete branch
// we want to stop at leaf and skip incomplete branch
private void traverseHelper(TreeNode root, 
                            int target, 
                            List<List<Integer>> paths, 
                            List<Integer> path) {
    // incomplete branch
    if (root == null) {
        return;
    }
    // leaf (the path right now is root->leaf)
    if (root.left == null && root.right == null) {
        if (target - root.val == 0) {
            path.add(root.val);
            paths.add(new ArrayList<>(path));
            path.remove(path.size() - 1);
        }
        return;
    }
    // traverse
    path.add(root.val);
    traverseHelper(root.left, target - root.val, paths, path);
    path.remove(path.size() - 1);

    path.add(root.val);
    traverseHelper(root.right, target - root.val, paths, path);
    path.remove(path.size() - 1);        
}