dfs

dfs的注意点：
	回复现场，也就是进入递归之前和退出递归的时候，状态是一样的
    有明确的结束的标记，也就是不能产生死循环

import java.util.*;

public class Solution {
    
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if(root != null)
            dfs(root,sum,ret,new ArrayList<Integer>(),0);
        return ret;
    }
    public void dfs(TreeNode node,int sum,ArrayList<ArrayList<Integer>> ret,ArrayList<Integer> list,int cur){
        cur += node.val;
        list.add(node.val);
        if(cur == sum && node.left == null && node.right == null){
            ArrayList<Integer> ele = new ArrayList<>(list);
            ret.add(ele);
        }
        if(node.left != null){
            dfs(node.left,sum,ret,list,cur);
        }
        if(node.right != null){
            dfs(node.right,sum,ret,list,cur);
        }
        list.remove(list.size() - 1);
        cur -= node.val;
    }
}