Path Sum II

1. Title

Path Sum II

2. Http address

https://leetcode.com/problems/path-sum-ii/

3. The question

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / 
            4   8
           /   / 
          11  13  4
         /      / 
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

4. My code (AC)

 1     public static void DFS(TreeNode root,List<Integer> list,int sum)
 2     {
 3 
 4             if( root == null )
 5                     return ;
 6             List<Integer> addlist = null;
 7             list.add(root.val);
 8             list.set(0,root.val + list.get(0));
 9             if( root.left == null && root.right == null )
10             {
11                 if( sum == list.get(0) )
12                 {
13                     addlist = new ArrayList<Integer>(list);
14                     addlist.remove(0);
15                     re.add(addlist);
16                 }
17             }
18 
19 
20             if( root.left != null )
21             {
22                 DFS(root.left,list,sum);
23                 list.set(0,list.get(0) - root.left.val);
24                 list.remove(list.size()-1);
25             }
26             if( root.right != null )
27             {
28                 DFS(root.right,list,sum);
29                 list.set(0,list.get(0) - root.right.val);
30                 list.remove(list.size()-1);
31             }
32             return;
33     }
34     //Accpeted
35     public static List<List<Integer>> pathSum(TreeNode root,int sum){
36 
37                 re = new ArrayList<List<Integer>>();
38                 if( root == null )
39                         return re;
40                 List<Integer> list = new ArrayList<Integer>();
41                 list.add(0);
42                 DFS(root,list,sum);
43                 return re;
44     }