本文共 1228 字,大约阅读时间需要 4 分钟。
题目:
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.
For example:
Given the below binary tree andsum = 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.
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution(object): def hasPathSum(self, root, sum): """ :type root: TreeNode :type sum: int :rtype: bool """ if root == None: return False if root.left == None and root.right==None: return sum==root.val return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)if __name__ == '__main__': l1_1 = TreeNode(1) l1_2 = TreeNode(2) l1_3 = TreeNode(3) l1_4 = TreeNode(4) l1_5 = TreeNode(5) l1_6 = TreeNode(6) l1_1.left = l1_2 l1_1.right = l1_3 l1_2.left = l1_4 l1_2.right = l1_5 l1_4.left = l1_6 l3 = Solution().hasPathSum(l1_1,34) print l3
转载地址:http://azhci.baihongyu.com/