Find tree path with sum equal to a number

Problem

Given a binary tree, find all the paths with sum equal to a target number.

A path starts at the root node, end at the the leaf node. Find all paths with the node sum equal to a number. 

For example, given the following binary tree and target number 10, the paths are 6 -> 3 -> 1 and 6 -> 4

      6

     / \

    3   4

   / \    \

  1   9   0

Solution

We can walk down from the root to the leaf, store the path. Once we reached the leaf, we can tell if the path nodes sum up to the target and store it. We need to pre-order traversal the nodes, the time cost is O(N). The space cost will be large if we allocate an array for each leaf. We can cut down the space cost by removing the current node from the shared list before returning to the caller. The space cost in that case normally O(logN), and be O(N) in worst case when the tree degrade to a linked list.

import java.util.*;
public class MatchingPath {
  private List<List<Node>> paths;
  private int target;
  public void matches(Node root, List<Node> path, int sum) {//6
    if(root.left == null && root.right == null) {
      sum += root.val;
      if(sum == target) {
        path.add(root);
        List<Node> path2 = new ArrayList<>();
        path2.addAll(path);
        paths.add(path2);
      }
      return;
    }
    path.add(root); //6->3->1;
    sum += root.val;  //6    ,9    ,10
    if(root.left != null)
      matches(root.left, path, sum);
    if(root.right != null)
      matches(root.right, path, sum);
    sum -= root.val;
    path.remove(root);
  }
  public MatchingPath(int target) {
    paths = new ArrayList<>();
    this.target = target;
  }
  public static void main(String...args) {
    MatchingPath mp = new MatchingPath(10);
    List<Node> path = new ArrayList<>();
    Node root = new Node(6, new Node(3, new Node(1, null, null), new Node(9, null, null)),
                         new Node(4, null, new Node(0, null, null)));
    mp.matches(root, path, 0);
    for(List<Node> list : mp.paths) {
      for(Node node : list) {
        System.out.print(node.val + " ");
      }
      System.out.println();
    }
  }
  private static class Node {
    int val;
    Node left;
    Node right;
    public Node(int val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}

Time cost O(N), space cost O(logN) to O(N).