队列与BFS
1.N叉树的层序遍历
使用BFS，即宽度优先搜索。把节点放入队列中，当节点出队列时让其孩子节点入队列，记录每层节点数量。
classSolution{public:vector<vector<int>>levelOrder(Node*root){vector<vector<int>>ret;queue<Node*>q;if(root==nullptr)returnret;q.push(root);while(!q.empty()){vector<int>v;intlen=q.size();//当前层节点数量for(inti=0;i<len;i++){Node*p=q.front();q.pop();v.push_back(p->val);for(Node*child:p->children)//下一层节点入队列if(child!=nullptr)q.push(child);}ret.push_back(v);}returnret;}};2.二叉树的锯齿形层序遍历
与上一题相似，锯齿形层序遍历时，可以照常从左到右遍历，把第一层记为level=1，每偶数层时逆序数组即可。也可以使用别的方法，只要能在偶数层逆序即可。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public:vector<vector<int>>zigzagLevelOrder(TreeNode*root){vector<vector<int>>ret;queue<TreeNode*>q;intflag=1;// 规定flag<0小于时逆序数组。if(root==nullptr)returnret;q.push(root);while(!q.empty()){intlen=q.size();vector<int>v;for(inti=0;i<len;i++){TreeNode*p=q.front();q.pop();v.push_back(p->val);if(p->left)q.push(p->left);if(p->right)q.push(p->right);}if(flag<0)//判断是否逆序数组reverse(v.begin(),v.end());flag*=-1;ret.push_back(v);}returnret;}};3.二叉树最大宽度
根据题意，如果直接按照前面题目的模板，会出现超出内存限制的情况。如下图所示，3000个节点分别位于两侧，中间全为空节点。
此时可以考虑树的顺序存储。即给树的每个节点从左到右，从上到下编号，如果从1开始编号，某个节点下标为x，则它的孩子节点为2x和2x+1。依旧使用循环+队列的模板，非空节点入队列，队列元素应使用pair类型，记录节点及其下标，每次循环取队头和队尾的下标做差再加1，即可求出一层的宽度。
题目保证最终的宽度在32位带符号的整数范围内，如果用int做差返回的宽度错误，用unsigned int则能够正确返回宽度。
classSolution{public:intwidthOfBinaryTree(TreeNode*root){queue<pair<TreeNode*,unsignedint>>q;unsignedintret=0;q.push({root,1});while(!q.empty()){autoe1=q.front();autoe2=q.back();ret=max(ret,e2.second-e1.second+1);size_t len=q.size();for(inti=0;i<len;i++){autop=q.front();q.pop();if(p.first->left)q.push({p.first->left,p.second*2});if(p.first->right)q.push({p.first->right,p.second*2+1});}}returnret;}};4.在每个树行中找最大值
与1、2题类似。只需用一个变量在遍历时记录最大值即可。
classSolution{public:vector<int>largestValues(TreeNode*root){queue<TreeNode*>q;vector<int>ret;if(root==nullptr)returnret;q.push(root);while(!q.empty()){intMax=INT_MIN;size_t len=q.size();for(inti=0;i<len;i++){TreeNode*p=q.front();q.pop();if(Max<p->val)Max=p->val;if(p->left)q.push(p->left);if(p->right)q.push(p->right);}ret.push_back(Max);}returnret;}};
