429. N 叉树的层序遍历
题目解析：
根据题目分析，可以看出题目要我们求的是N叉数的层序遍历，就是把每层的放在一块，最后把每层都输出出来即可！
算法分析：
我们可以利用队列先进先出的特性进行求解，这里比层序遍历多了一个条件，记录当前层有多少个节点，然后只把当前层的节点出完即可，就是一层一层的进行输出，我们需要记录每层的节点的值，所以我们应该使用一个vector存储每层的节点，然后最终将每层的结点放到最终的vector中即可！
代码：
class Solution {
public:
vector<vector<int>> levelOrder(Node* root)
{
//定义一个队列用于进行出队的操作！
queue<Node*> q;
vector<vector<int>>ret;
//首先判断给定的根节点是否为空，为空的话直接结束！
if(root==nullptr)
{
return ret;
}
//不为空！
q.push(root);
//当队中一直存在元素时，一直进行遍历即可！
while(q.size())
{
//统计出本层的节点个数！
//只需要进行出队len次，即可完成本次的出队操作！！
int len=q.size();
for(int i=0;i<len;i++)
{
Node*tem=q.front(); //队头元素！
q.pop();
v.push_back(tem->val); //将本层节点的值进行放入到vector中！
for(Node* child:tem->children)
{
//本次元素出队之后，将其孩子进行入队操作！
if(child)
{
q.push(child);
}
}
}
ret.push_back(v);
}
return ret;
}
};103. 二叉树的锯齿形层序遍历
题目解析：
根据题目分析我们可以得出，题目要让我们第一次进行从左向右遍历，第二层进行从右向左遍历，如此往复，返回最终遍历的结果！
算法分析：
对于本题，还是和之前二叉树的变量一样，只不过是多了一个条件而言，相邻的每行的遍历顺序恰好相反，所以我们可以设置一个flag变量，用于标志何时进行逆置即可！当flag满足逆置的条件时，我们把本层结点的vector进行reverse即可！
代码
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root)
{
vector<vector<int>>ret;
queue<TreeNode*>q;
if(root==nullptr)
{
return ret;
}
int flag=1;
q.push(root);
while(q.size())
{
int len=q.size();
//奇数为从左向右，偶数相反！
//直接全部使用从左向右，对于偶数的情况！！我们只需要将得到的vector进行reverse然后再插入即可！
vector<int>v;
for(int i=0;i<len;i++)
{
TreeNode*tem=q.front();
q.pop();
v.push_back(tem->val);
//下一层元素进行入队！
//左右孩子入队列！
if(tem->left)
{
q.push(tem->left);
}
if(tem->right)
{
q.push(tem->right);
}
}
if(flag==-1)
{
reverse(v.begin(),v.end());
}
ret.push_back(v);
flag*=-1;
}
return ret;
}
};
662. 二叉树最大宽度
题目解析：
根据题目分析，我们可以得出题目要我们求出二叉树的最大宽度，其中最大宽度的定义为最左和左右的非空节点之间的长度！
算法分析：
我们可以利用堆中下标的思想，进行求解，我们在堆那边有一个公式，当根节点下标为0时，左孩子下标为2*parent+1,右孩子下标为左孩子+1。当根节点为1时，左孩子下标为2*parent,右孩子仍然是左孩子+1，根据下标的特性，我们可以求出二叉树的最大宽度！
代码：
class Solution {
public:
int widthOfBinaryTree(TreeNode* root)
{
vector<pair<TreeNode*, unsigned int>> q; // ⽤数组模拟队列
q.push_back({root, 1});
unsigned int ret = 0;
while(q.size())
{
// 先更新这⼀层的宽度
auto&[x1, y1]= q[0];
auto&[x2, y2]= q.back();
ret = max(ret, y2 - y1 + 1);
// 让下⼀层进队
vector<pair<TreeNode*, unsigned int>> tmp; // 让下⼀层进⼊这个队列
for(auto& [x,y] : q)
{
if(x->left) tmp.push_back({x->left, y * 2});
if(x->right) tmp.push_back({x->right, y * 2 + 1});
}
q= tmp;
}
return ret;
}
};515. 在每个树行中找最大值
题目解析：
根据题目简单的介绍，我们可以得出题目要出的答案就是获取每层的最大值，然后进行push到结果数组中即可！
算法讲解：
还是和N叉数的层序遍历一样，我们还是需要记录的每层结点的个数，只不过本次我们需要引进一个新的变量，用于记录每层的最大值即可，我们开始将此变量置为INT_MIN即可！
代码：
class Solution {
public:
vector<int> largestValues(TreeNode* root)
{
queue<TreeNode*>q;
vector<int>ret;
if(root==nullptr)
{
return ret;
}
q.push(root);
//当队列不为空的时候，一直进行循环即可！
while(q.size())
{
int m=INT_MIN;
//求出本层的结点个数！
int len=q.size();
for(int i=0;i<len;i++)
{
TreeNode*tem=q.front();
q.pop();
if(tem->val>m)
{
m=tem->val;
}
//把下一层的元素压入到队列中！
if(tem->left)
{
q.push(tem->left);
}
if(tem->right)
{
q.push(tem->right);
}
}
ret.push_back(m);
}
return ret;
}
};至此，本专题总结完毕，有疑问的小伙伴可以在评论区进行讨论。
