-
Notifications
You must be signed in to change notification settings - Fork 0
/
LevelOrderII.cpp
63 lines (52 loc) · 1.6 KB
/
LevelOrderII.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
//
// Created by Wanhui on 3/11/20.
//
#include <deque>
#include "LevelOrderII.h"
std::vector<std::vector<int>> Solution32_2::levelOrder(BiTreeNode *root) {
if (root == nullptr) {
return {};
}
// 存放数组的数组
std::vector<std::vector<int>> ans;
// 存放每一层的节点数组
std::vector<int> levelAns;
// 存放节点的队列
std::deque<BiTreeNode *> deq;
// 将根节点入队
deq.push_back(root);
// 初始化下一层节点数
int nextCount = 0;
// 初始化本层未出队节点数
int levelCount = 1;
while (!deq.empty()) {
BiTreeNode *popNode = deq.front();
levelAns.push_back(popNode->val);
// 左节点入队,下一层节点数加一
if (popNode->left != nullptr) {
deq.push_back(popNode->left);
nextCount++;
}
// 右节点入队,下一层节点数加一
if (popNode->right != nullptr) {
deq.push_back(popNode->right);
nextCount++;
}
// 本层节点出队,本层未出队节点数减一
deq.pop_front();
levelCount--;
// 本层节点全部出队时
if (levelCount == 0) {
// 将本层全部节点存入结果数组
ans.push_back(levelAns);
// 将本层数组置空
levelAns = {};
// 将下一层的节点数赋给本层,
// 重新开始新的一轮
levelCount = nextCount;
// 下一轮的子节点数重新开始计数
nextCount = 0;
}
}
return ans;
}