剑指offer-二叉树中和为某一值的路径

题目描述：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路：回溯

ac代码：

 1 import java.util.ArrayList;
 2 /**
 3 public class TreeNode {
 4     int val = 0;
 5     TreeNode left = null;
 6     TreeNode right = null;
 7 
 8     public TreeNode(int val) {
 9         this.val = val;
10 
11     }
12 
13 }
14 */
15 public class Solution {
16     public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
17         if(root!=null)
18         dfs(root,target,0);
19         return list;
20     }
21      ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
22      ArrayList<Integer>list2=new ArrayList<Integer>();
23      void dfs(TreeNode p,int target,int sum){
24         list2.add(p.val);
25          if(p.left==null&&p.right==null){
26             if(sum+p.val==target){
27                 ArrayList<Integer> t=new ArrayList<Integer>();
28                 for(int i=0;i<list2.size();i++){
29                     t.add(list2.get(i));
30                 }
31                 list.add(t);    
32             }
33         }
34         if(p.left!=null){
35             dfs(p.left,target,sum+p.val);
36             list2.remove(list2.size()-1);
37         }
38         if(p.right!=null){
39             dfs(p.right,target,sum+p.val);
40             list2.remove(list2.size()-1);
41         }
42         
43     }
44 }