-
Notifications
You must be signed in to change notification settings - Fork 0
/
Path_Sum.cpp
27 lines (25 loc) · 906 Bytes
/
Path_Sum.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 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.
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
if (root == NULL)
return false;
if (root->left == NULL && root->right == NULL && sum-root->val == 0)
return true;
if (root->left == NULL && root->right == NULL && sum-root->val != 0)
return false;
return hasPathSum(root->left, sum-root->val) ||
hasPathSum(root->right, sum-root->val);
}
};