队列宽搜 -1

目录

1.简介

2.例题

2.1N叉树的层序遍历

2.2二叉树的锯齿形层序遍历

2.3二叉树最大宽度

2.4在每个树行中找最大值

---

1.简介

没什么好说的，宽搜就是利用队列，一层层向外搜。这里是刷题，就不详细说宽搜内容了

2.例题

2.1N叉树的层序遍历

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>> ans(0);if(root==nullptr)return ans;queue<Node*> mp;mp.push(root);int level = 1;int nextlevel = 0;vector<int>b(0);while (!mp.empty()) {auto tmp = mp.front();b.push_back(tmp->val);level--;mp.pop();for (auto x : tmp->children) {if(x==nullptr)continue;mp.push(x);nextlevel++;}if (level == 0) {ans.push_back(b);b.clear();level = nextlevel;nextlevel = 0;}}return ans;}
};

2.2二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

暴力模拟，利用一个栈，每隔一层使节点顺序倒一次

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ans(0);queue<TreeNode*> mp;if (root == nullptr)return ans;mp.push(root);int way = 1;while (!mp.empty()) {vector<int> b;int level = mp.size();stack<TreeNode*> brief;for (int i = 0; i < level; i++) {auto tmp = mp.front();b.push_back(tmp->val);if (way == 1) {if (tmp->left)brief.push(tmp->left);if (tmp->right)brief.push(tmp->right);} else {if (tmp->right)brief.push(tmp->right);if (tmp->left)brief.push(tmp->left);}mp.pop();}ans.push_back(b);if (way == 0) {while (brief.size()) {mp.push(brief.top());brief.pop();}way = 1;} else {while (brief.size()) {mp.push(brief.top());brief.pop();}way = 0;}}return ans;}
};

接下来是不用额外空间的思路,只需要标记偶数行，让偶数行存的值，进行逆序即可。

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ans(0);queue<TreeNode*> mp;if (root == nullptr)return ans;mp.push(root);int level=1,nextlevel=0;int way = 1;vector<int> b;while (!mp.empty()) {auto tmp=mp.front();b.push_back(tmp->val);mp.pop();level--;if(tmp->left)mp.push(tmp->left),nextlevel++;if(tmp->right)mp.push(tmp->right),nextlevel++;if(level==0){level=nextlevel;if(way%2==0)reverse(b.begin(),b.end());ans.push_back(b);nextlevel=0;b.clear();way++;}}return ans;}
};

2.3二叉树最大宽度

662. 二叉树最大宽度 - 力扣（LeetCode）

利用数组存二叉树的时候，找孩子节点下标的公式，让队列里也记录这个下标，这样就能直接利用下标得到宽度了。

注意，这题int*2会溢出，所以用无符号int存就行了，（不能long long,因为long long也存不了这么多，但是无符号int可以无视溢出，不管是否溢出，相减的结果就是我们的答案）

class Solution {
public:int widthOfBinaryTree(TreeNode* root) {unsigned int ans=0;queue<pair<TreeNode*,unsigned int>>mp;if(root==nullptr)return ans;mp.push({root,1});unsigned int level=1,nextlevel=0;unsigned int pre=1;while(mp.size()){auto tmp=mp.front();mp.pop();level--;if(tmp.first->left)mp.push({tmp.first->left,tmp.second*2}),nextlevel++;if(tmp.first->right)mp.push({tmp.first->right,tmp.second*2+1}),nextlevel++;if(level==0){level=nextlevel;nextlevel=0;ans=max(ans,tmp.second-pre+1);pre=mp.front().second;}}return ans;}
};

2.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) {queue<TreeNode*>mp;vector<int>ans;if(root==nullptr)return ans;mp.push(root);while(mp.size()){int sz=mp.size();int res;int f=0;for(int i=0;i<sz;i++){auto tmp=mp.front();mp.pop();if(f==0)res=tmp->val,f=1;else res=max(res,tmp->val);if(tmp->left)mp.push(tmp->left);if(tmp->right)mp.push(tmp->right);}ans.push_back(res);}return ans;}
};