1
class Solution {
2
  public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
3
    List<List<Integer>> ans = new ArrayList<>();
4
    pathSum(root, targetSum, new ArrayList<>(), ans);
5
    return ans;
6
  }
7

8
  public void pathSum(TreeNode root, int targetSum, List<Integer> path, List<List<Integer>> ans) {
9
    if (root == null) return;
10
    path.add(root.val);
11
    if (root.left == null
12
        && root.right == null
13
        && targetSum == root.val) // leaf node that completes path
14
    {
15
      ans.add(
16
          new ArrayList(
17
              path)); // we use new ArrayList because if we don't the originaly List is added which
18
      // is mutable, if we add a copy that's not mutable.
19
    } else {
20
      pathSum(root.left, targetSum - root.val, path, ans);
21
      pathSum(root.right, targetSum - root.val, path, ans);
22
    }
23
    path.remove(path.size() - 1); // removal of redundant nodes
24
  }
25
}