Given a binary tree and a number sum, compute the sum along each path from the root to every leaf node. Determine whether any leaf node’s path sum equals sum.
This problem can be solved with BFS by enumerating all paths, but watch the edge cases: it must be a leaf node, and consider the cases where the root has no children or is null.
Code below:
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
TreeNode ** seq = new TreeNode*[10000];
TreeNode ** rseq = new TreeNode*[10000];
if(root == NULL)
return false;
else
{
if(root->left == NULL && root->right == NULL)
{
if(root->val == sum)
return true;
else
return false;
}
int index = 0;
seq[index++] = root;
while(true)
{
int top = index;
index = 0;
for(int i = 0;i < top;i++)
{
if(seq[i] != NULL)
{
if(seq[i]->left != NULL)
{
seq[i]->left->val += seq[i]->val;
rseq[index++] = seq[i]->left;
if(seq[i]->left->val == sum && seq[i]->left->left == NULL && seq[i]->left->right == NULL)
return true;
}
if(seq[i]->right != NULL)
{
seq[i]->right->val += seq[i]->val;
rseq[index++] = seq[i]->right;
if(seq[i]->right->val == sum && seq[i]->right->left == NULL && seq[i]->right->right == NULL)
return true;
}
}
}
if(index == 0)
break;
for(int i = 0;i < index;i++)
{
seq[i] = rseq[i];
}
}
return false;
}
}
};
|