113-路径总和II

力扣113

https://leetcode-cn.com/problems/path-sum-ii/

虽然树和回溯本质上都是DFS，但我更愿意把这个选择+递归+撤销的模式归为回溯

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

private List<List<Integer>> res = new ArrayList<>();
public void findPath(TreeNode root, int remain, List<Integer> path) {
    //结束条件
    if (root == null) return ;

    //选择
    path.add(root.val);
    if (root.left == null && root.right == null && remain - root.val == 0){
        res.add(new ArrayList<>(path));
    }

    //递归
    findPath(root.left, remain - root.val, path);
    findPath(root.right, remain - root.val, path);
    
    //撤销
    path.remove(path.size() - 1);
}