113. 路径总和 II

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

解法一：dfs回溯

与112题相比，dfs过程中加一个tmp记录当前路径即可，满足条件就将这条路径写入结果集。

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        self.res = []   #结果集
        tmpList = []    #记录路径
        self.dfs(root, tmpList, sum)
        return self.res
    
    def dfs(self, root, tmpList, sum):
        if not root:
            return
        tmpList.append(root.val)    #尝试将root的值加入路径
        #符合条件写入
        if not root.left and not root.right and root.val == sum:
            self.res.append(list(tmpList))
        self.dfs(root.left, tmpList, sum-root.val)
        self.dfs(root.right, tmpList, sum-root.val)
        tmpList.pop()    #恢复现场

也可以简化回溯代码，但是速度不如上面快，估计list拼接增加了时间开销

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        self.res = []   #结果集
        tmpList = []
        self.dfs(root, tmpList, sum)
        return self.res
    
    def dfs(self, root, tmpList, sum):
        if not root:
            return
        if not root.left and not root.right and root.val == sum:
            self.res.append((tmpList+[root.val]))    #这里可以不新建list，因为拼接操作创建了一个新 list
        self.dfs(root.left, tmpList+[root.val], sum-root.val)
        self.dfs(root.right, tmpList+[root.val], sum-root.val)