PathSumII.java

import java.util.ArrayList;

/**
 * Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given
 * sum.
 *
 * <p>For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
 * return [ [5,4,11,2], [5,8,4,5] ]
 */
public class PathSumII {
  public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if (root != null) {
      ArrayList<Integer> path = new ArrayList<Integer>();
      findPathSum(root, sum, result, path);
    }
    return result;
  }

  public void findPathSum(
      TreeNode root, int sum, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> path) {
    if (root == null) return;
    if (root.left == null && root.right == null && root.val == sum) {
      ArrayList<Integer> clone = new ArrayList<Integer>(path);
      clone.add(root.val);
      result.add(clone);
    } else {
      path.add(root.val);
      if (root.left != null) {
        findPathSum(root.left, sum - root.val, result, path);
      }
      if (root.right != null) {
        findPathSum(root.right, sum - root.val, result, path);
      }
      path.remove(path.size() - 1);
    }
  }
}