113. Path Sum II

和binary tree paths那道题差不多，第一步可以先写出一个返回所有路径的列表的递归函数，返回值为空。也是分三种情况讨论，空节点，最后一个节点和中间节点。注意python求中间结果的时候的不要指向同一个list。在空节点的情况中其实if not root: return可以等价为

if root.left: do sth..
if root.right: do sth..

def dfs(self, root, path, res):
    if not root: return
    if not root.left and not root.right:
        path.append(root.val)
        res.append(path)
    self.dfs(root.left, path + [root.val], res)
    self.dfs(root.right, path + [root.val], res)

然后根据题意在递归的时候加入sum条件判断，以及if root.val != sum: return这个条件。

def pathSum(self, root, sum):
    """
    :type root: TreeNode
    :type sum: int
    :rtype: List[List[int]]
    """
    res = []
    self.dfs(root, [], res, sum)
    return res

def dfs(self, root, path, res, sum):
    if not root: return
    if not root.left and not root.right:
        if root.val != sum: return
        path.append(root.val)
        res.append(path)
    self.dfs(root.left, path + [root.val], res, sum - root.val)
    self.dfs(root.right, path + [root.val], res, sum - root.val)

不过照这么写真的很慢。因为每次递归都会生成两个新的list。

public void dfs(TreeNode root, List<Integer>path, List<List<Integer>> res, int sum) {
    if (root == null) return;
    if (root.left == null && root.right == null) {
        if (root.val != sum) return;
        path.add(root.val);
        res.add(path);
        return;
    }
    path.add(root.val);
    dfs(root.left, new ArrayList<>(path), res, sum - root.val);
    dfs(root.right, new ArrayList<>(path), res, sum - root.val);
}

然后就有了这种操作。path相当于一个栈，酱紫就减少了创建list的次数。

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(root, path, res, sum);
    return res;
}
public void dfs(TreeNode root, List<Integer>path, List<List<Integer>> res, int sum) {
    if (root == null) return;
    path.add(root.val);
    sum -= root.val
    if (root.left == null && root.right == null && sum == 0) {
        res.add(new ArrayList<>(path));
    }
    dfs(root.left, path, res, sum);
    dfs(root.right, path, res, sum);
    path.remove(path.size() - 1);
}