-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlevelSum.cpp
More file actions
77 lines (69 loc) · 1.42 KB
/
Copy pathlevelSum.cpp
File metadata and controls
77 lines (69 loc) · 1.42 KB
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <queue>
#define method1 1
#define method2 0
class TreeNode
{
public:
int val;
TreeNode *left, *right;
TreeNode(int val)
{
this->val = val;
this->left = this->right = NULL;
}
};
class Solution
{
public:
#if method1
int levelSum(TreeNode *root, int level)
{
dfs(root, 1, level);
return sum;
}
void dfs(TreeNode *root, int depth, int level)
{
if(root == NULL) return;
if(depth == level)
{
sum += root->val;
}
dfs(root->left, depth + 1, level);
dfs(root->right, depth + 1, level);
}
private:
int sum = 0;
#endif
#if method2
int levelSum(TreeNode *root, int level)
{
if(root == NULL) return 0;
std::queue<TreeNode*> q;
q.push(root);
int l = 0, sum = 0;
while(q.size())
{
++l;
int size = q.size();
for(int i = 0; i < size; ++i)
{
TreeNode *node = q.front();
q.pop();
if(node->left != NULL)
{
q.push(node->left);
}
if(node->right != NULL)
{
q.push(node->right);
}
if(l == level)
{
sum += node->val;
}
}
}
return sum;
}
#endif
};