队列&&宽搜 -1
目录
1.简介
没什么好说的，宽搜就是利用队列，一层层向外搜。这里是刷题，就不详细说宽搜内容了
2.例题
2.1N叉树的层序遍历
/* // 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二叉树最大宽度
利用数组存二叉树的时候，找孩子节点下标的公式，让队列里也记录这个下标，这样就能直接利用下标得到宽度了。
注意，这题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; } };
原文地址：https://blog.csdn.net/MXZSL/article/details/142497049
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！