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

     */

    int target = 0;

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {

        // write your code here

        if(root == null){

            return res;

        }

        this.target = target;

        List<Integer>path = new ArrayList<>();

        helper(path, root, 0);

        return res;

    }

    public void helper(List<Integer>path, TreeNode root, int sum){

        sum +=root.val;

        path.add(root.val);

        //如果到叶子结点了，并且和为target

        if(root.left == null && root.right == null && sum == target){

            ArrayList<Integer>temp = new ArrayList<>();

            temp.addAll(path);//复制一份

            res.add(temp);

        }

        if(root.left != null){

            helper(path, root.left, sum);

        }

        if(root.right != null){

            helper(path, root.right, sum);

        }

        path.remove(path.size() - 1);

    }

}