题解 | #求二叉树的层序遍历#
求二叉树的层序遍历
https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3
class Solution {
public:
//固定值
const static int MAXSIZE =150;
//返回值列表
vector<vector<int > >vec;
//层遍历值列表
vector<int >cp;
//指向每一层的元素的指针列表
TreeNode* QUEUE[MAXSIZE];
int Front = 0; //指向队列头的指针
int Rare = 0; //指向队列尾的指针
int Length = 0;//队列元素长度计数器
int p = 0; //指向当层的最后一个元素
vector<vector<int> > levelOrder(TreeNode* root) {
if (root != nullptr) {
//我们需要初始化我们的整个队列
if (root->left != nullptr) {
QUEUE[Rare] = root->left;
Rare = (Rare + 1) % MAXSIZE;
Length++;
}
if (root->right != nullptr) {
QUEUE[Rare] = root->right;
Rare = (Rare + 1) % MAXSIZE;
Length++;
}
p = Rare - 1;
//将根节点的值保存进入我们的层序列表中
cp.push_back(root->val);
vec.push_back(cp);
cp.clear();//清空整个数组的垃圾数据
while (Length != 0) {
if (Front != p) {
if (QUEUE[Front]->left != nullptr) {
QUEUE[Rare] = QUEUE[Front]->left;
Rare = (Rare + 1) % MAXSIZE;
Length++;
}
if (QUEUE[Front]->right != nullptr) {
QUEUE[Rare] = QUEUE[Front]->right;
Rare = (Rare + 1) % MAXSIZE;
Length++;
}
//将该节点的值压入我们的数组中，并删除该结点
cp.push_back(QUEUE[Front]->val);
Front = (Front + 1) % MAXSIZE;
Length--;
}
else {
if (QUEUE[Front]->left != nullptr) {
QUEUE[Rare] = QUEUE[Front]->left;
Rare = (Rare + 1) % MAXSIZE;
Length++;
}
if (QUEUE[Front]->right != nullptr) {
QUEUE[Rare] = QUEUE[Front]->right;
Rare = (Rare + 1) % MAXSIZE;
Length++;
}
//将该节点的值压入我们的数组中
cp.push_back(QUEUE[Front]->val);
Front = (Front + 1) % MAXSIZE;
Length--;
vec.push_back(cp);
cp.clear();//清空整个数组
//更新新的指向该层最后一个元素的指针
p = Rare - 1;
}
}
}
return vec;
}
};
