1. 题目描述

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

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

返回:

[
[5,4,11,2],
[5,8,4,5]
]

2. 思路

还是利用递归，不过要记录每一步的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