LeetCode——路径总和II

NO.113 路径总和II 中等

思路一：深搜回溯 NO.112路径总和的姊妹题，区别在于本题要求拿到路径集合，这样本题就更像NO.39组合总和、NO.40组合总和II了。思路也差不多：回溯。

每次减去节点值，并将节点加入路径集合。

需要注意的是：路径集合放入结果集之后，要remove当前节点之后再返回。不然会出现路径带有分支的情况，例如下图：

List<List<Integer>> res = new LinkedList<>();

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    dfs(root, sum, new LinkedList<Integer>());
    return res;
}

private void dfs(TreeNode root, int sum, LinkedList<Integer> track) {
    if (root == null) return;
    //减去当前节点值，节点加入路径
    sum -= root.val;
    track.add(root.val);
    //如果到达叶子节点并且路径和等于sum
    if (root.left == null && root.right == null && sum == 0) {
        res.add(new LinkedList<>(track));
        track.removeLast();//注意，返回前要removeLast
        return;
    }
    //左右子树
    dfs(root.left, sum, track);
    dfs(root.right, sum, track);
    //回溯
    track.removeLast();
}

时间复杂度：O(n) 不能确定：虽然是回溯思路，每个节点只访问了一次。

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github