队列+宽搜专题篇

N叉树的层序遍历

二叉树的锯齿形层序遍历

二叉树最大宽度

在每个树行中找最大值

N叉树的层序遍历

题目

思路

使用队列+层序遍历来解决这道题，首先判断根节点是否为空，为空则返回空的二维数组；否则，就进行层序遍历，将每层节点依次取出，放入到二维数组中，并将取出的节点的孩子依次添加到队列中，最后返回二维数组。

代码

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.empty()){int sz=q.size();vector<int> v;while(sz--){Node* tp=q.front();q.pop();v.push_back(tp->val);for(Node* child:tp->children)if(child!=nullptr) q.push(child);}ret.push_back(v);}return ret;}
};

二叉树的锯齿形层序遍历

题目

思路

使用队列+层序遍历来解决这道题，不过需要对偶数层的结果进行逆置，可以使用一个变量来记录当前层的层数，或者使用一个布尔变量来记录当前层是否是偶数层，将每层节点依次取出，如果当前层是偶数层，需要先将数组进行逆置，然后再将数组放入到二维数组中，并将取出的节点的孩子依次添加到队列中，最后返回二维数组。

代码

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ret;if(root==nullptr) return ret;queue<TreeNode*> q;q.push(root);bool flag=false;while(!q.empty()){int sz=q.size();vector<int> v;while(sz--){TreeNode* node=q.front();q.pop();v.push_back(node->val);if(node->left) q.push(node->left);if(node->right) q.push(node->right);}if(flag) reverse(v.begin(),v.end());ret.push_back(v);flag=!flag;}return ret;}
};

二叉树最大宽度

题目

思路

首先我们可能会想到下面的方法，将空节点也加入到队列中，然后统计每一次一层非空节点之间空节点的数量，然后+2就是二叉树该行的最大宽度，但是这道题有可能是第二张图那种倒V型，这样就会导致我们队列存储的节点数量非常之多，因此这种方法看起来可行，但实际上是行不通的。

我们可能会想到对每个节点进行编号（受使用数组建堆的启发），根节点的编号可以从0开始也可以从1开始，虽然编号可能会溢出，但是差值是正确的，但是如果我们使用int来存储，溢出时会报错，因此我们使用unsigned int来存储宽度，解法依旧是使用队列+层序遍历，步骤和前几道题是一样的。

代码

class Solution {
public:int widthOfBinaryTree(TreeNode* root) {vector<pair<TreeNode*,unsigned int>> q;q.push_back({root,1});unsigned int ret=0;while(!q.empty()){auto [a,b]=q[0];auto [c,d]=q.back();ret=max(ret,d-b+1);vector<pair<TreeNode*,unsigned int>> v;for(auto [x,y]:q){if(x->left) v.push_back({x->left,2*y});if(x->right) v.push_back({x->right,2*y+1});}q=v;}return ret;}
};

在每个树行中找最大值

题目

思路

使用队列+层序遍历来解决这道题，步骤和前几道题是一样的，无非是在遍历每一层时，将每一层的最大值记录下来，最后返回数组。

代码

class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> ret;if(root==nullptr) return ret;queue<TreeNode*> q;q.push(root);while(!q.empty()){int sz=q.size();vector<int> v;while(sz--){TreeNode* node=q.front();q.pop();v.push_back(node->val);if(node->left) q.push(node->left);if(node->right) q.push(node->right);}ret.push_back(*max_element(v.begin(),v.end()));}return ret;}
};