//注意，1，要判断null；2，要注意ArrayList直接复制会被一起改变。要通过new的方式来操作。
public class Solution {

    public static void main(String[] args){

        TreeNode root = new TreeNode(10);

        root.left = new TreeNode(5);

        root.right = new TreeNode(12);

        root.left.left = new TreeNode(4);

        root.left.right = new TreeNode(7);

        ArrayList<ArrayList<Integer>> test = FindPath(null,22);

        for(ArrayList<Integer> tmp : test){

            System.out.println(tmp);

        }

    }

    public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {

        ArrayList<ArrayList<TreeNode>> res = new ArrayList();

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

        if(root == null || root.val > target  ) return ans;

        ArrayList<TreeNode> tmp = new ArrayList();

        tmp.add(root);

        res.add(tmp);

        int flag = 1;

        while(flag != 0){

            System.out.println(123);

            flag = 0;

            ArrayList<ArrayList<TreeNode>> res2 = new ArrayList();

            for(ArrayList<TreeNode> a : res){

                ArrayList<TreeNode> left = new ArrayList(a);

                ArrayList<TreeNode> right = new ArrayList(a);

                TreeNode tmp1 = a.get(a.size()-1).left;

                TreeNode tmp2 = a.get(a.size()-1).right;

                if(tmp1 != null ){

                    System.out.println("tmp1=" + tmp1.val);

                    left.add(tmp1);

                    res2.add(left);

                    flag = 1;

                }

                if(tmp2 != null ){

                    right.add(tmp2);

                    res2.add(right);

                    flag = 1;

                }

                if(tmp1 == null && tmp2 == null){

                    res2.add(left);

                }

            }

            res = new ArrayList(res2);

            for(ArrayList<TreeNode> a : res){

                for(TreeNode t : a){

                    System.out.print(t.val+" ");

                }

                System.out.println("");

            }

            System.out.println(flag);

            System.out.println("res.size()="+ res.size());

        }

        for(ArrayList<TreeNode> a : res){

            if(sum(a) == target){

                ArrayList<Integer> al = new ArrayList();

                for(TreeNode t : a){

                    al.add(t.val);

                }

                ans.add(al);

            }

        }

        return ans;

    }

    public static int sum (ArrayList<TreeNode> tmp){

        int sum = 0;

        for(TreeNode t : tmp){

            sum += t.val;

        }

        return sum;

    }

}