## Leetcode: path sum | (Python)

A good function 2020-11-13 02:53:43
leetcode path sum python

## 1. Title Description

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]
]

## 2. Ideas

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
``````