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