1、前言

2、思路

使用回溯的基本思路：先遍历这个节点，再去掉，一直到根节点为止。

3、代码

class Solution {

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if(root == null){
            return new ArrayList<>();
        }
        dfs(root, target, new ArrayList<>());

        return res;
    }

    private void dfs(TreeNode root, int target, List<Integer> list){
        if(root == null){
            return;
        }

        // 不用减枝，因为有负数
//        if(target - root.val < 0){
//            return;
//        }

        // 到最后一个节点就该判断了，要不然下面到递归会重复两次
        if(root.left == null && root.right == null && target - root.val == 0){
            list.add(root.val);
            res.add(new ArrayList<>(list));
            list.remove(list.size() - 1);
            return;
        }

        list.add(root.val);
        dfs(root.left, target - root.val, list);
        dfs(root.right,target - root.val, list);
        list.remove(list.size() - 1);
    }
}