113. 路径总和 II(中)

• 题目
• 题解：回溯

题目

• 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

题解：回溯

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

    def dfs(self, root, target, res, path):
        if not root:#空结点
            return
        if sum(path) == target and not root.left and not root.right:
            res.append(path[:])# 将满足条件的路径添加到结果列表中
        if root.left:#递归遍历左子树
            self.dfs(root.left, target, res, path + [root.left.val])
        if root.right:# 递归遍历右子树
            self.dfs(root.right, target, res, path + [root.right.val])
        path.pop()#撤销选择，回溯到上一层