JZ24 二叉树中和为某一值的路径,dfs

dfs1

public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ans=new ArrayList<>();
        if(root==null) return ans;
        ArrayList<Integer> list=new ArrayList<>();
        list.add(root.val);
        dfs(root, target-root.val, list);
        return ans;
    }
    ArrayList<ArrayList<Integer>> ans;
    void dfs(TreeNode root, int target, ArrayList<Integer> list){
        if(root.left==null&&root.right==null){
            if(target==0) ans.add(new ArrayList<Integer>(list));
            return;
        }
        if(root.left!=null){
            list.add(root.left.val);
            dfs(root.left, target-root.left.val, list);
            list.remove(list.size()-1);
        }
        if(root.right!=null){
            list.add(root.right.val);
            dfs(root.right, target-root.right.val, list);
            list.remove(list.size()-1);
        }     
        return;
    }
}

dfs2

public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ans=new ArrayList<>();
        if(root==null) return ans;
        ArrayList<Integer> list=new ArrayList<>();
        //list.add(root.val);
        dfs(root, target, list);
        return ans;
    }
    ArrayList<ArrayList<Integer>> ans;
    void dfs(TreeNode root, int target, ArrayList<Integer> list){
        if(root==null) return;
        target-=root.val;
        list.add(root.val);
        if(root.left==null&&root.right==null){
            if(target==0) ans.add(new ArrayList<Integer>(list));
            list.remove(list.size()-1);
            return;
        }
        dfs(root.left, target, list);
        dfs(root.right, target, list);  
        list.remove(list.size()-1);
        return;
    }
}

这里无法绕开的是，list每一次都需要remove。就像dfs中visited[]先为true后为false一样。
如果不想这么做，解决办法有两个

1. 每次递归时，new一个ArrayList
2. 最终确定路径存在的时候才生成list，每一次往list的前面添加元素。