# Q112 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.

##### 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.```

##### Python实现：
```# 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, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if root == None:
return False
if sum - root.val == 0 and root.left == None and root.right == None: # 如果累积到当前结点结果正好为0且是叶子结点
return True
else:
return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val) # 只需要找到一条路径即可```

161 篇文章42 人订阅

0 条评论

## 相关文章

11110

### 通过BitSet完成对单词使用字母的统计

BitSet类实现了一组位或标记（flag）,这些位可被分别设置或清除。当需要跟踪一组布尔值时，这种类很有用。

12220

29180

9930

1.6K100

38040

54680

288100

9840

17640