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;}
};