-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
102.cpp
80 lines (80 loc) · 2.47 KB
/
102.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
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
78
79
80
__________________________________________________________________________________________________
8ms
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode* pRoot) {
vector<pair<int,int>> vec;
vector<vector<int>> ans;
if(pRoot==nullptr)
return ans;
queue<pair<TreeNode*,int>> q;
q.push(make_pair(pRoot,1));
while(!q.empty()){
pair<TreeNode*,int> now=q.front();
q.pop();
vec.push_back(make_pair(now.first->val,now.second));
if(now.first->left)
q.push(make_pair(now.first->left,now.second+1));
if(now.first->right)
q.push(make_pair(now.first->right,now.second+1));
}
vector<int> v;
for(int i=0;i<vec.size();i++){
if(i!=0&&vec[i].second!=vec[i-1].second){
ans.push_back(v);
v.clear();
}
v.push_back(vec[i].first);
}
ans.push_back(v);
return ans;
}
};
__________________________________________________________________________________________________
13532 kb
/**
* 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:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> result{1, vector<int>{}};
queue<TreeNode*> nodes{};
nodes.push(root);
nodes.push(nullptr);
int resultIndex = 0;
while(!nodes.empty()) {
auto next = nodes.front();
nodes.pop();
if (!next) {
if (nodes.empty()) break;
nodes.push(nullptr);
++resultIndex;
result.push_back(vector<int>{});
} else {
result[resultIndex].push_back(next->val);
if (next->left) nodes.push(next->left);
if (next->right) nodes.push(next->right);
}
}
return result;
}
};
__________________________________________________________________________________________________