Amazon Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
class Node:
def __init__(self):
self.left = None
self.right = None
self.val = 0
def hasSum(root, target_sum):
_, found = getSum(root, target_sum)
return found
def getSum(root, target_sum):
if root is None:
return 0, False
left_sum, found = getSum(root.left, target_sum)
if found:
return 0, found
right_sum, found = getSum(root.right, target_sum)
if found:
return 0, found
s = root.val + left_sum + right_sum
found = bool(s == target_sum)
return s, found
- Mikhail August 12, 2017