给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
还是利用递归,不过要记录每一步的root.val。
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
if root == None:
return []
temp = []
result = []
return self.dfs(root,sum,temp,result)
def dfs(self,root,sum,tempPath,res):
if root == None:
return res
if root.val == sum and not root.left and not root.right:
# 如果相等且为叶节点,将root加入字结果中,并将直接过加入res
tempPath += [root.val]
res.append(tempPath)
# 继续向下递归
self.dfs(root.left,sum-root.val,tempPath+[root.val],res)
self.dfs(root.right,sum-root.val,tempPath+[root.val],res)
return res