1
 / \
 2 4
 / \
 2 3

[
 [1, 2, 2],
 [1, 4]
]

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *  public int val;
 *  public TreeNode left, right;
 *  public TreeNode(int val) {
 *   this.val = val;
 *   this.left = this.right = null;
 *  }
 * }
 */
public class Solution {
 /**
  * @param root the root of binary tree
  * @param target an integer
  * @return all valid paths
  */
 public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
  // Write your code here
  return dfs(root,new ArrayList<Integer>(),0,new ArrayList<List<Integer>>(),target);
 }
 public List<List<Integer>> dfs(TreeNode root,List<Integer> node, int sum, List<List<Integer>> paths,int target)
  {
  if(root==null)
    {
   return new ArrayList<List<Integer>>();
  }
  List<List<Integer>> path=new ArrayList<List<Integer>>();
  if(root.left!=null)
    {
   List<Integer> nodes=new ArrayList<Integer>();
   if(node!=null)
     {
    nodes.addAll(node);
   }
   nodes.add(root.val);
   List<List<Integer>> temp=dfs(root.left,nodes,sum+root.val,paths,target);
   if(temp!=null)
      {
    path.addAll(temp);
   }
  }
  if(root.right!=null)
    {
   List<Integer> nodes=new ArrayList<Integer>();
   if(node!=null)
     {
    nodes.addAll(node);
   }
   nodes.add(root.val);
   List<List<Integer>> temp=dfs(root.right,nodes,sum+root.val,paths,target);
   if(temp!=null)
      {
    path.addAll(temp);
   }
  }
  if(root.left==null&&root.right==null)
    {
   List<Integer> nodes=new ArrayList<Integer>();
   if(node!=null)
     {
    nodes.addAll(node);
   }
   nodes.add(root.val);
   if(sum+root.val==target)
      {
    path.add(nodes);
   } else{
    path=new ArrayList<List<Integer>>();
   }
  }
  return path;
 }
}