C++算法：队列与BFS

队列与BFS1.N叉树的层序遍历使用BFS即宽度优先搜索。把节点放入队列中当节点出队列时让其孩子节点入队列记录每层节点数量。classSolution{public:vectorvectorintlevelOrder(Node*root){vectorvectorintret;queueNode*q;if(rootnullptr)returnret;q.push(root);while(!q.empty()){vectorintv;intlenq.size();//当前层节点数量for(inti0;ilen;i){Node*pq.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.二叉树的锯齿形层序遍历与上一题相似锯齿形层序遍历时可以照常从左到右遍历把第一层记为level1每偶数层时逆序数组即可。也可以使用别的方法只要能在偶数层逆序即可。/** * 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:vectorvectorintzigzagLevelOrder(TreeNode*root){vectorvectorintret;queueTreeNode*q;intflag1;// 规定flag0小于时逆序数组。if(rootnullptr)returnret;q.push(root);while(!q.empty()){intlenq.size();vectorintv;for(inti0;ilen;i){TreeNode*pq.front();q.pop();v.push_back(p-val);if(p-left)q.push(p-left);if(p-right)q.push(p-right);}if(flag0)//判断是否逆序数组reverse(v.begin(),v.end());flag*-1;ret.push_back(v);}returnret;}};3.二叉树最大宽度根据题意如果直接按照前面题目的模板会出现超出内存限制的情况。如下图所示3000个节点分别位于两侧中间全为空节点。此时可以考虑树的顺序存储。即给树的每个节点从左到右从上到下编号如果从1开始编号某个节点下标为x则它的孩子节点为2x和2x1。依旧使用循环队列的模板非空节点入队列队列元素应使用pair类型记录节点及其下标每次循环取队头和队尾的下标做差再加1即可求出一层的宽度。题目保证最终的宽度在32位带符号的整数范围内如果用int做差返回的宽度错误用unsigned int则能够正确返回宽度。classSolution{public:intwidthOfBinaryTree(TreeNode*root){queuepairTreeNode*,unsignedintq;unsignedintret0;q.push({root,1});while(!q.empty()){autoe1q.front();autoe2q.back();retmax(ret,e2.second-e1.second1);size_t lenq.size();for(inti0;ilen;i){autopq.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*21});}}returnret;}};4.在每个树行中找最大值与1、2题类似。只需用一个变量在遍历时记录最大值即可。classSolution{public:vectorintlargestValues(TreeNode*root){queueTreeNode*q;vectorintret;if(rootnullptr)returnret;q.push(root);while(!q.empty()){intMaxINT_MIN;size_t lenq.size();for(inti0;ilen;i){TreeNode*pq.front();q.pop();if(Maxp-val)Maxp-val;if(p-left)q.push(p-left);if(p-right)q.push(p-right);}ret.push_back(Max);}returnret;}};