/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> resList=new ArrayList<List<Integer>>();

    public void path(TreeNode r,ArrayList<Integer> list,int sum)
    {
        if(r.right==null && r.left==null)
        {
            int res=0;
            for(int i=0;i<list.size();i++)
                res+=list.get(i);
            if(res==sum)
                resList.add(list);
        }
        else if(r.right!=null && r.left!=null)
        {
            ArrayList<Integer> leftList= new ArrayList<Integer>();
            ArrayList<Integer> rightList= new ArrayList<Integer>();

            for(int i=0;i<list.size();i++)
            {
                leftList.add(list.get(i));
                rightList.add(list.get(i));
            }

            rightList.add(r.right.val);
            path(r.right,rightList,sum);

            leftList.add(r.left.val);
            path(r.left,leftList,sum);
        }
        else if(r.right!=null && r.left==null)
        {
            ArrayList<Integer> rightList= new ArrayList<Integer>();
            for(int i=0;i<list.size();i++)
               rightList.add(list.get(i));

            rightList.add(r.right.val);
            path(r.right,rightList,sum);
        }
        else
        {
            ArrayList<Integer> leftList= new ArrayList<Integer>();
            for(int i=0;i<list.size();i++)
                leftList.add(list.get(i));
            leftList.add(r.left.val);
            path(r.left,leftList,sum);
        }
    }

    public List<List<Integer>> findPath(TreeNode root, int sum) {
        ArrayList<Integer> list= new ArrayList<Integer>();
        if(root==null && sum==0)
            return resList;
        list.add(root.val);
        path(root,list,sum);
        return resList;
    }
}