leetcode112 -- Path Sum

# 小郑之家~

### 题目


Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path 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      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.



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

class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
return self.helper(root, sum)

def helper(self, root, target):
if not root:
return False
if not root.left and not root.right:
if root.val == target:
return True
else:
return False

if root.left and not root.right:
return self.helper(root.left, target-root.val)
if not root.left and root.right:
return self.helper(root.right, target-root.val)

if root.left and root.right:
return self.helper(root.left, target-root.val) or self.helper(root.right, target-root.val)



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

class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
return self.helper(root, sum)

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

if not root.left and not root.right:
if root.val == target:
return True
else:
return False

elif root.left and not root.right:
return self.helper(root.left, target-root.val)
elif not root.left and root.right:
return self.helper(root.right, target-root.val)
else:
return self.helper(root.left, target-root.val) or self.helper(root.right, target-root.val)



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

class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
res = []
self.helper(root, res, [])

# get res
print(res)
for x in res:
summ =0
for y in x:
summ += y
if summ == sum:
return True

return False

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[:])