层序遍历的基本概念
层序遍历说白了就是按照每一层从左到右的顺序去进行遍历。
实现的基本逻辑
实现的基本逻辑就是用一个队列去存储每一层的元素，存在队列里了然后就是去遍历这一层，因为会记录队列的size，因此会确保访问的是一层元素
代码实现
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> res;
if(root==nullptr)
{ // null直接返回
return res;
}
// 根节点先入队
que.push(root);
while(!que.empty())
{ // 定义一个临时数组保存
vector<int> temp;
// 数组的size来确保访问的是一层
int size = que.size();
for(int i=0; i<size; i++)
{ // 保存队头节点
TreeNode *cur = que.front();
que.pop(); // 出队
temp.push_back(cur->val); // 进遍历数组
// 该节点的左右孩子进队
if(cur->left!=nullptr)
{
que.push(cur->left);
}
if(cur->right!=nullptr)
{
que.push(cur->right);
}
}
// 将当前一层访问的压入res数组中
res.push_back(temp);
}
return res;
}
};
下面是9道leetcode上的题目，用层序遍历来做
leetcode 107
题目描述
简单来说就是反着的层序遍历，那么我们正着遍历最后reverse一下即可
代码实现
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> res;
if(root==nullptr)
{
return res;
}
que.push(root);
while(!que.empty())
{
vector<int> temp;
int size = que.size();
for(int i=0; i<size; i++)
{
TreeNode *cur = que.front();
que.pop();
temp.push_back(cur->val);
if(cur->left!=nullptr)
{
que.push(cur->left);
}
if(cur->right!=nullptr)
{
que.push(cur->right);
}
}
res.push_back(temp);
}
// 与之前的层序遍历不同之处
reverse(res.begin(), res.end());
return res;
}
};
leetcode 199
题目描述
从题目来看就是找到每一层的最右节点即每层队列中的最后一个节点，那么仅需在层序遍历中加入判断条件即可
代码实现
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> que;
vector<int> temp;
if(root==nullptr)
{
return temp;
}
que.push(root);
while(!que.empty())
{
int size = que.size();
for(int i=0; i<size; i++)
{
TreeNode *cur = que.front();
que.pop();
if((size-i)==1)
{ // 判断是否是该层中的最后一个元素
temp.push_back(cur->val);
}
if(cur->left!=nullptr)
{
que.push(cur->left);
}
if(cur->right!=nullptr)
{
que.push(cur->right);
}
}
}
return temp;
}
};
leetcode 637
题目描述
题目也很简单，只需要层序遍历的时候算一个平均数即可
代码实现
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
queue<TreeNode*> que;
vector<double> res;
if(root==nullptr)
{
return res;
}
que.push(root);
while(!que.empty())
{
int size = que.size();
// 定义和
double sum = 0;
// 定义平均数
double ave = 0;
for(int i=0; i<size; i++)
{
TreeNode *cur = que.front();
que.pop();
sum += cur->val;// 计算和
if(cur->left!=nullptr)
{
que.push(cur->left);
}
if(cur->right!=nullptr)
{
que.push(cur->right);
}
}
ave = sum/size;// 计算平均数
res.push_back(ave);
}
return res;
}
};
leetcode 429
题目描述
这个题目基本和二叉树一样，只是后面push进节点的时候遍历孩子节点即可
代码实现
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
queue<Node*> que;
if(root==NULL)
{
return res;
}
que.push(root);
while(!que.empty())
{
int size = que.size();
vector<int> temp;
for(int i=0; i<size; i++)
{
Node *cur = que.front();
temp.push_back(cur->val);
que.pop();
// 将孩子节点进队
for(int j=0; j<cur->children.size(); j++)
{
if(cur->children[j]!=NULL)
{
que.push(cur->children[j]);
}
}
}
res.push_back(temp);
}
return res;
}
};
leetcode 515
题目描述
同样还是层序遍历，只不过迭代最大值即可
代码实现
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> res;
queue<TreeNode*> que;
if(root==nullptr)
{
return res;
}
que.push(root);
while(!que.empty())
{
int size = que.size();
// 设置最大值是层的第一个元素
int max = que.front()->val;
for(int i=0; i<size; i++)
{
TreeNode *cur = que.front();
que.pop();
// 判断是否是最大值进行迭代
if(max<cur->val)
{
max = cur->val;
}
if(cur->left!=nullptr)
{
que.push(cur->left);
}
if(cur->right!=nullptr)
{
que.push(cur->right);
}
}
res.push_back(max);
}
return res;
}
};
leetcode 116 117
题目描述
116的题目是完美二叉树， 117不是完美二叉树，但是用层序遍历来做都是一样的
只需要在每层遍历的时候赋值一下next指针的指向即可
代码实现
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> que;
if(root==NULL)
{
return root;
}
que.push(root);
while(!que.empty())
{
int size = que.size();
for(int i=0; i<size; i++)
{
Node *cur = que.front();
que.pop();
if((size-i)==1)
{ // 判断是否是最后一个元素
cur->next = NULL;
}else
{ // 不是最后一个元素进行next指针的赋值
cur->next = que.front();
}
if(cur->left!=NULL)
{
que.push(cur->left);
}
if(cur->right!=NULL)
{
que.push(cur->right);
}
}
}
return root;
}
};
leetcode 104
题目描述
这个题用层序遍历也好做，只需要遍历到最后一层，弄个计数器累加即可
代码实现
class Solution {
public:
int maxDepth(TreeNode* root) {
int depth = 0;
queue<TreeNode*> que;
if(root==nullptr)
{
return depth;
}
que.push(root);
while(!que.empty())
{
int size = que.size();
for(int i=0; i<size; i++)
{
TreeNode *cur = que.front();
que.pop();
if(cur->left!=nullptr)
{
que.push(cur->left);
}
if(cur->right!=nullptr)
{
que.push(cur->right);
}
}
// 每遍历完一层进行++
depth++;
}
return depth;
}
};
leetcode 111
题目描述
上一题求最大深度，这次求最小深度，那么只要一遇到无孩子的节点就应该返回
代码实现
class Solution {
public:
int minDepth(TreeNode* root) {
int depth = 0;
queue<TreeNode*> que;
if(root==nullptr)
{
return depth;
}
que.push(root);
while(!que.empty())
{
int size = que.size();
// 这里的不同就是++在前面 因为后面会返回所以提前加加
depth++;
for(int i=0; i<size; i++)
{
TreeNode *cur = que.front();
que.pop();
if(cur->left==nullptr && cur->right==nullptr)
{ // 遇到叶子节点返回
return depth;
}
if(cur->left!=nullptr)
{
que.push(cur->left);
}
if(cur->right!=nullptr)
{
que.push(cur->right);
}
}
}
return depth;
}
};
本文含有隐藏内容，请 开通VIP 后查看