leetcode题解113：路径总和 II

描述

该题来自于力扣第113题

分析

典型的dfs了，函数参数应该有 当前结点，前面的路径以及剩下的和（总和减去前面路径的和） 即dfs(root, sum, path)，接下来需要考虑什么是否路径正确，以及函数退出条件。

显然当root没有左右结点，且root的值等于sum时，表示路径总和等于给的总和，此时path添加root结点就是一条目标路径；

而当root有左节点或右节点时，显然继续递归，这时现将path路径添加上root结点，然后递归左子树dfs(root.left, sum - root.val, path)，右子树dfs(root.left, sum - root.val, path)；注意当左右子树都遍历完后，表示以root为结点的子树遍历完成了，此时path需要回溯到之前的状态，保证遍历root的兄弟结点时，root已经不在path中了。

最后递归结束条件即可。

代码

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        self.all_path = []
        self.dfs(root, targetSum, [])
        return self.all_path

    def dfs(self, root, sum_, path):
        if root is None:
            return
        path.append(root.val)
        if root.left is None and root.right is None and sum_ == root.val:
            self.all_path.append(path[:])

        self.dfs(root.left, sum_ - root.val, path)
        self.dfs(root.right, sum_ - root.val, path)
        path.pop()