For 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.
Solution:
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a boolean
def hasPathSum(self, root, sum):
return self.hasPathSumRec(root, sum, 0)
def hasPathSumRec(self, root, sum, tempSum):
if root == None:
return False
if root.left == None and root.right == None:
return tempSum+root.val == sum
return self.hasPathSumRec(root.left, sum, tempSum + root.val) or self.hasPathSumRec(root.right, sum, tempSum + root.val)
No comments :
Post a Comment