回溯法DFS

import java.util.ArrayList;

public class 根节点到叶子节点的路径和 {

/**
 * 使用回溯法，从根节点开始。每遍历一个节点，就将该节点的值放入路径中，
 * 判断是否为叶子节点，当前nowsum是否与sum相等，
 * 相等就将list加入到结果中，否则回退，回退要将list的最后一个元素删除。
 */
ArrayList<ArrayList<Integer>> res=new ArrayList<>();
public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
    // write code here
    ArrayList<Integer> path=new ArrayList<>();
    if (root==null)return res;
    dfs(root,0,sum,path); 
    return res;
}

public void dfs(TreeNode root, int nowsum, int sum, ArrayList<Integer> list){
    list.add(root.val);
    //判断是否为叶子节点，当前nowsum是否与sum相等，
    if (root.right==null&&root.left==null&&sum==(nowsum+root.val)){
        //相等就将list加入到结果中，
        res.add(new ArrayList<>(list));return;
    }
    if (root.left!=null) {
        dfs(root.left,nowsum+root.val,sum,list);
        list.remove(list.size()-1);
    }
    if (root.right!=null){
        dfs(root.right,nowsum+root.val,sum,list);
        list.remove(list.size()-1);
    }
}

}