# 112.Path Sum(Tree-Easy)

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.

Language ： python

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
if not root.left and not root.right and root.val == sum:
return True
sum -= root.val
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)```

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
elif not root.left and not root.right and root.val == sum:
return True
for child in (root.left, root.right):
if child:
if self.hasPathSum(child, sum - root.val):
return True
return False```

Language : cpp

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL) return false;
else if (root->val == sum && root->left ==  NULL && root->right == NULL) return true;
if (root->left && hasPathSum(root->left, sum - root->val)) return true;
if (root->right && hasPathSum(root->right, sum - root->val)) return true;
return false;
}
};```

LeetCode题目汇总： https://github.com/Jack-Cherish/LeetCode

0 条评论

## 相关文章

571

1492

### 第十九天 集合-Map接口容器工具类集合框架总结【悟空教程】

Map集合的特点，如是否可重复，是否有序仅作用在键上，如HashMap集合的键不得重复，值可以重复。

1983

1592

3607

2326

### 读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现，可以避免一些错误的用法。

972

1453

### 【计算机本科补全计划】Java学习笔记(九) Java日期时间

### 1、 Java 日期时间 java.util 包提供了 Date 类来封装当前的日期和时间。 Date 类提供两个构造函数来实例化 Date 对象。第一...

932

1182