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
