Given a binary tree and a target and , Find all paths from the root node to the leaf node whose total path is equal to the given target and .
explain : A leaf node is a node that has no children .
Example :
Given the following binary tree , And goals and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return :
[
[5,4,11,2],
[5,8,4,5]
]
Or recursion , But record every step 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:
# If they are equal and leaf nodes , take root Add to the word result , And will directly add res
tempPath += [root.val]
res.append(tempPath)
# Continue recursion down
self.dfs(root.left,sum-root.val,tempPath+[root.val],res)
self.dfs(root.right,sum-root.val,tempPath+[root.val],res)
return res