优选算法——队列+BFS

目录

1. N叉树的层序遍历

2.  二叉树的锯齿层序遍历

3. 二叉树最大宽度

4. 在每个树行中找最大值

---

1. N叉树的层序遍历

题目链接：429. N 叉树的层序遍历 - 力扣（LeetCode）

题目展示：

题目分析：

层序遍历即可~仅需多加⼀个变量，用来记录每⼀层结点的个数就好了。

代码实现：

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/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.size()){int sz=q.size();//记录当前层节点个数vector<int> tmp;//统计本层节点for(int i=0;i<sz;i++){Node* t=q.front();q.pop();tmp.push_back(t->val);for(Node* child:t->children)//让下一层节点入队{if(child!=nullptr){q.push(child);}}}ret.push_back(tmp);}return ret;}
};

2.  二叉树的锯齿层序遍历

题目链接：103. 二叉树的锯齿形层序遍历 - 力扣（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:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ret;if(root==nullptr){return ret;}queue<TreeNode*> q;q.push(root);int level=1;while(q.size()){int sz=q.size();vector<int> tmp;for(int i=0;i<sz;i++){auto t=q.front();q.pop();tmp.push_back(t->val);if(t->left) q.push(t->left);if(t->right) q.push(t->right);}//判断是否需要逆序if(level%2==0) reverse(tmp.begin(),tmp.end());ret.push_back(tmp);level++;}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) {vector<pair<TreeNode*,unsigned int>> q;q.push_back({root,1});unsigned int ret=0;while(q.size()){//先更新这一层的宽度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;}
};

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:vector<int> largestValues(TreeNode* root) {vector<int> ret;if(root==nullptr) return ret;queue<TreeNode*> q;q.push(root);while(q.size()){int sz=q.size();int tmp=INT_MIN;for(int i=0;i<sz;i++){auto t=q.front();q.pop();tmp=max(tmp,t->val);if(t->left) q.push(t->left);if(t->right) q.push(t->right);}ret.push_back(tmp);}return ret;}
};