1. N叉树的层序遍历
首先我们遇到这个题目，没有任何思路，我们就可以来模拟一下层序的流程，首先我们肯定是访问根节点1，访问之后呢就是访问下一层的最左节点3，此时第一层的节点1已经访问过了就可以不要了，然后访问第二层的中间节点2，最后访问最右边的节点4，然后就访问第三层，此时第二层最做节点就不要了，此时我们会发现此时就满足队列的先进先出的特点，知道用什么数据结构了我们就直接上思路：
直接上代码：
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ret; //记录最终结果
queue<Node*> q; // 层序遍历需要的队列
if(root == nullptr)
return ret;
q.push(root); // 队头元素入队
while(!q.empty())
{
vector<int> tmp; //统计本层的节点
int size = q.size(); //求出本层元素的个数
while(size--)
{
Node* n = q.front();
q.pop();
tmp.push_back(n->val);
for(auto child : n->children) // 让孩子入队列
{
if(child != nullptr)
q.push(child);
}
}
ret.push_back(tmp);
}
return ret;
}
};2. 二叉树的锯齿形层序遍历
这个题目上给我们说了层序遍历，那么我们还是要用到队列，我们会发现，这道题和我们上道题目是一样的都是层序遍历，唯一的区别就是偶数层的遍历方式是我们之前的逆序，所以这道题目也很简单，直接上思路：
直接来写代码：
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;
queue<TreeNode*> q;
int flag = 1;//增加一个标记位,让偶数行的信息逆序即可
if(root == nullptr) return ret;
q.push(root);
while(!q.empty())
{
vector<int> tmp;
int size = q.size();
while(size--)
{
TreeNode* front = q.front();
q.pop();
tmp.push_back(front->val);
if(front->left != nullptr)
q.push(front->left);
if(front->right != nullptr)
q.push(front->right);
}
if(flag == 1)
ret.push_back(tmp);
else
{
reverse(tmp.begin(),tmp.end());
ret.push_back(tmp);
}
flag *= -1;
}
return ret;
}
};3. 在每个树行中找最大值
我们这道题和之前的题目思路是一样的，只不过这个题目我们不需要统计每层的节点，只需要统计最大的哪一个节点即可，所以在层序遍历过程中，在执⾏让下⼀层节点⼊队的时候，我们可以在循环中统计出当前层结点的最大值的，直接上思路：
直接来写代码：
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> ret;
if(root == nullptr) return ret;
queue<TreeNode*> q;
q.push(root);
while(q.size()) // 如果队列不为空
{
int maxnum = INT_MIN;
int size = q.size();
while(size--)
{
TreeNode* t = q.front();
q.pop();
maxnum = max(maxnum, t->val); // 记录每层的最大值
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
ret.push_back(maxnum);
}
return ret;
}
};4.二叉树的最大宽度
题目解析：
这道题相较于上面三道题就有点难度了，这个题目男难就难在处理空节点，既然统计每一层的最大宽度，我们优先想到的就是利用层序遍历，把当前层的结点全部存在队列⾥面，利用队列的常度来计算每一层的宽度，统计出最大的宽度。但是，由于空节点也是需要计算在内的。因此，我们可以选择将空节点也存在队列⾥⾯。
⭐解法一：
这个思路是我们正常会想到的思路，但是极端境况下，最左边⼀条长链，最右边⼀条长链，我们需要存几亿个空节点，会超过最⼤内存限制。
⭐解法二：利用数组存储二叉树的方式，给节点编号
依旧是利⽤层序遍历，但是这⼀次队列⾥⾯不单单存结点信息，并且还存储当前结点如果在数组中存储所对应的下标（在我们学习数据结构堆的时候，计算左右孩子的方式）。
这样我们计算每⼀层宽度的时候，⽆需考虑空节点，只需将当层结点的左右结点的下标相减再加 1即可，我们直接上思路：
魔鬼细节：
极端境况下，最左边⼀条长链，最右边⼀条长链，我们需要存几亿个空节点，会超过最⼤内存限制，那么此时我们的编号是2的1500次方，那么肯定会越界，此时无论什么数据类型我们都存不下，但是这个题最后我们是会进行减法的，但是我们数据的存储是⼀个环形的结构，并且题⽬说明，数据的范围在 int 这个类型的最大值的范围之内，因此不会超出⼀圈； 因此，如果是求差值的话，我们⽆需考虑溢出的情况，由于c++溢出使用int会报错，因此我们使用unsigned int来存储这个数据。直接上代码：
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
queue<pair<TreeNode*, unsigned int>> q;
q.push({root,1}); // 根节点和编号入队
unsigned int ret = 0; // 最大宽度
while(q.size())
{
// 先更新这⼀层的宽度
auto& [x1, y1] = q.front();
auto& [x2, y2] = q.back();
ret = max(ret, y2 - y1 + 1);
int size = q.size();
// 让下⼀层进队
while(size--)
{
auto [a,b] = q.front();
q.pop();
if(a->left) q.push({a->left, 2*b});
if(a->right) q.push({a->right,2*b+1});
}
}
return ret;
}
};其实这道题我们也可以用数组来实现，但是这时候有人说了此时我们会经常进行删除节点，而删除节点都是头删，而数组的头删效率较低，你咋还使用我们的数组呢？确实是这样，但是我们进行删除节点不一定要头删，我们可以把本层的节点用tmp统计出来，然后拷贝给q即可。
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
vector<pair<TreeNode*,unsigned int>> q; // 用数组模拟队列
q.push_back(make_pair(root,1));
unsigned int ret = 0;
while(!q.empty())
{
// 先更新这⼀层的宽度
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;
}
};
