题目
- 给你二叉树的根节点 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()#撤销选择，回溯到上一层