Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree andsum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

Analysis

Similar to Path Sum I, using DFS to find the path with a targeted sum, yet it requires additional space to store the intermediate results, thus creating helper function with temporal results argument.

One tricky part is to add root.val to the temporal results first and check if it matches targeted sum (passed in), if so remove it from temporal results, because the same temporal list will be used in a different branch as well

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> paths = new LinkedList<List<Integer>>();
        List<Integer> currentPath = new LinkedList<Integer>();
        if (root == null) return paths;
        pathSumHelper(root, sum, currentPath, paths);
        return paths;
    }
    void pathSumHelper(TreeNode root, int sum, List<Integer> currentPath, List<List<Integer>> paths) {
        if (root == null) return;
        currentPath.add(new Integer(root.val));
        if (root.val == sum && root.left == null && root.right == null) {
            paths.add(new LinkedList(currentPath));
            // remember to remove the last element for upper level recursive call
            currentPath.remove(currentPath.size() - 1); 
            return;
        } else {
            pathSumHelper(root.left, sum - root.val, currentPath, paths);
            pathSumHelper(root.right, sum - root.val, currentPath, paths);
        }
        // remember to remove the last element for upper level recursive call
        currentPath.remove(currentPath.size() - 1); 
    }
}

Simplify Back-tracking

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<List<Integer>> allValidPaths;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        allValidPaths = new ArrayList<>();
        traverse(root, sum, 0, new ArrayList<>());
        return allValidPaths;
    }

    private void traverse(TreeNode node, int sum, int currSum, List<Integer> sumPath) {
        if(node == null) return;

        currSum += node.val;
        sumPath.add(node.val);
        if(node.left == null && node.right == null && currSum == sum) {
            allValidPaths.add(new ArrayList<>(sumPath));
        }
        else {
            traverse(node.left, sum, currSum, sumPath);
            traverse(node.right, sum, currSum, sumPath);
        }

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

Simplify Helper Function

class Solution {
    private List<List<Integer>> allValidPaths;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        allValidPaths = new ArrayList<>();
        traverse(root, sum, new ArrayList<>());
        return allValidPaths;
    }

    private void traverse(TreeNode node, int sum, List<Integer> sumPath) {
        if(node == null) return;

        sumPath.add(node.val);
        if(node.left == null && node.right == null && node.val == sum) {
            allValidPaths.add(new ArrayList<>(sumPath));
        }
        else {
            traverse(node.left, sum - node.val, sumPath);
            traverse(node.right, sum - node.val, sumPath);
        }

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