C++算法（13）队列+宽搜

1.N叉树的层序遍历429. N 叉树的层序遍历 - 力扣LeetCode首先将N叉树的根节点放入队列中当队列中存在元素则进入循环保存此时队列元素的个数因为要将队列个数的节点出队头每出一个队头则将此队头的子节点入队每次循环即是提取该层元素并将下层元素全部入队的过程注意细节若子节点为空则不入队那么最后一层出队完毕后也不会有节点入队退出最外层循环代码如下/* // Definition for a Node. class Node { public: int val; vectorNode* children; Node() {} Node(int _val) { val _val; } Node(int _val, vectorNode* _children) { val _val; children _children; } }; */ class Solution { public: vectorvectorint levelOrder(Node* root) { vectorvectorint ret; queueNode* q; if(rootnullptr) { return ret; } q.push(root); while(q.size()) { int szq.size(); Node* tq.front(); vectorint tmp; while(sz--) { tmp.push_back(t-val); for(auto n:t-children) { if(n!nullptr) { q.push(n); } } q.pop(); tq.front(); } ret.push_back(tmp); } return ret; } };2.二叉树的锯齿形层序遍历103. 二叉树的锯齿形层序遍历 - 力扣LeetCode和上一题的大逻辑基本相同只需要注意提取到的层数组是否需要反转后再插入ret即可可以多设一个变量作为判断标志代码如下/** * 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) {} * }; */ class Solution { public: vectorvectorint zigzagLevelOrder(TreeNode* root) { vectorvectorint ret; if(rootnullptr) { return ret; } queueTreeNode* q; q.push(root); int flag1; while(q.size()) { int szq.size(); vectorint tmp; while(sz--) { TreeNode* rq.front(); if(r-left) { q.push(r-left); } if(r-right) { q.push(r-right); } tmp.push_back(r-val); q.pop(); } flag-flag; if(flag1) { reverse(tmp.begin(),tmp.end()); } ret.push_back(tmp); } return ret; } };3.二叉树的最大宽度662. 二叉树最大宽度 - 力扣LeetCode储存节点时多存一个二叉树下标以键值对的方式储存可以不存在队列里直接以数组的方式储存对于每一层节点取出第一个节点和最后一个节点的下标值求出长度即可获得层宽代码如下/** * 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) {} * }; */ class Solution { public: int widthOfBinaryTree(TreeNode* root) { vectorpairTreeNode*,unsigned intret; pairTreeNode*,unsigned int pre(root,1); ret.push_back(pre); unsigned int len1; while(ret.size()) { //先更新这一层的长度 auto [x1,y1]ret[0]; auto [x2,y2]ret.back(); lenmax(len,y2-y11); //让下一层进队 vectorpairTreeNode*,unsigned int tmp; for(auto [x,y]:ret) { if(x-left) { tmp.push_back({x-left,y*2}); } if(x-right) { tmp.push_back({x-right,y*21}); } } rettmp; } return len; } };4.在每个树行中找最大值515. 在每个树行中找最大值 - 力扣LeetCode这道题其实已经不难了在常规的层序遍历的逻辑的基础上加上一个在每一层更新最大值的逻辑即可。代码如下/** * 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) {} * }; */ class Solution { public: vectorint largestValues(TreeNode* root) { queueTreeNode* q; vectorint ret; if(rootnullptr) { return ret; } q.push(root); while(q.size()) { int szq.size(); int nINT_MIN; while(sz--) { TreeNode* rq.front(); if(r-left) { q.push(r-left); } if(r-right) { q.push(r-right); } nmax(n,r-val); q.pop(); } ret.push_back(n); } return ret; } };