leetcode113 -- Path Sum II

# 小郑之家~

### 题目

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

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

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




# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:

res = []
self.helper(root, sum ,res, [])
return res

def helper(self, root, target, res, out):
if not root:
return

out.append(root.val)

if not root.left and not root.right:
if root.val == target:
res.append(out[:])
out.pop()

elif not root.left and root.right:
self.helper(root.right, target-root.val, res, out)
elif root.left and not root.right:
self.helper(root.left, target-root.val, res, out)
else:
self.helper(root.left, target-root.val, res, out[:])
self.helper(root.right, target-root.val, res, out[:])




class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:

res = []
self.helper(root, sum ,res, [])
return res

def helper(self, root, target, res, out):
if not root:
return

out.append(root.val)
if not root.left and not root.right and root.val == target:
res.append(out[:])
out.pop()

self.helper(root.left, target-root.val, res, out[:])
self.helper(root.right, target-root.val, res, out[:])



# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:

res = []
self.helper(root, res ,[])
ret = []
for x in res:
summ = 0
for y in x:
summ += y

if summ==sum:
ret.append(x)

return ret

def helper(self, root, res, out):
if not root:
return

out.append(root.val)
if not root.left and not root.right:
res.append(out[:])

self.helper(root.left, res, out[:])
self.helper(root.right, res,out[:])