LeetCode 113：路径总和 II

链接

题目：

思路：dfs

思路类似零钱兑换 ，每次向下递归时，把要凑的数sum 减去当前节点root的val，这样即得到下一层需要凑的钱，直到叶子节点的sum等于节点则将path添加到 r ！

由于要从根节点一路添加节点到path，所以是前序遍历；

要得到多个路径，使用类似排列组合的方法：①选择 ②递归 ③撤回
选择的时候，满足条件就将path添加到 r，遍历完再撤回，维护一个path用来存储路径的和；

class Solution {
    
    List<List<Integer>> r=new LinkedList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
    
        dfs(root,sum);
        return r;
    }

    void dfs(TreeNode root,int sum){
    
        if(root==null){
    
            return;
        }
        // 选择
        path.add(root.val);
            // 如果是叶子节点且满足sum才添加！
        if(root.left==null && root.right==null && sum==root.val){
    
            r.add(new LinkedList(path));
        }

        // 递归
        dfs(root.left,sum-root.val);
        dfs(root.right,sum-root.val);
        
        // 撤回
        path.removeLast();
    }

}