算法笔记（十）——队列＋宽搜

BFS是图上最基础、最重要的搜索算法之一；
每次都尝试访问同一层的节点如果同一层都访问完了，再访问下一层

BFS基本框架

void bfs(起始点)
{将起始点放入队列中;标记起点已访问;while(队列不为空){访问队列中首元素;删除队首元素;for(队首元素所有相邻点){if(该点未被访问过且合法)将该点加入队列末尾; }}宽搜结束; 
} 

N 叉数的层序遍历

题目：N 叉数的层序遍历

思路

• BFS（宽搜）
• 创建vector<vector<int>> ret来保存结果；
• 创建queue<Node*> q来将根节点入队，如果根节点为空则直接返回空的ret
• 当队列不为空的时候一直循环：
• • 获取当前队列大小
• • 用vector<int> tmp来统计本层节点
• • 出队头元素，保存在tmp中，若其孩子节点非空，则进入队列
• • 每层节点出队后，将其保存在tmp中的节点，push_back进ret

C++代码

/*
// 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 n = q.size(); // 本层元素个数vector<int> tmp;  // 统计本层节点for(int i = 0; i < n; 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;}
};

二叉树的锯齿形层序遍历

题目：二叉树的锯齿形层序遍历

思路1

• 和上一题的思路一样，我们先封装一个函数vector<vector<int>> levelOrder(TreeNode *root)正常层序遍历该二叉树，将其结果存储在vector<vector<int>> ret
• 再对结果ret进行逆序，当为偶数层时，对其结果进行逆序；

C++代码

/*** 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 = levelOrder(root);// 偶数层时，对其结果进行逆序for (int i = 1; i < ret.size(); i += 2)reverse(ret[i].begin(), ret[i].end());return ret;}vector<vector<int>> levelOrder(TreeNode *root){vector<vector<int>> ret;if (!root)return ret;queue<TreeNode* > q;q.push(root);while (q.size()){int n = q.size();vector<int> tmp;for(int i = 0; i < n; i++){TreeNode* t = q.front();tmp.push_back(t->val);q.pop();if(t->left) q.push(t->left);if(t->right) q.push(t->right);}ret.push_back(tmp);}return ret;}
};

思路2
我们也可以添加一个标记位flag，当奇数层时，正常添加到结果数组，偶数层时，逆序后进入结果数组

C++代码

/*** 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)return ret;queue<TreeNode* > q;q.push(root);int flag = 0; // 标志层数while (q.size()){flag++;int n = q.size();vector<int> tmp;for(int i = 0; i < n; i++){TreeNode* t = q.front();tmp.push_back(t->val);q.pop();if(t->left) q.push(t->left);if(t->right) q.push(t->right);}if(flag % 2 == 0) reverse(tmp.begin(), tmp.end()); // 偶数层逆序后再进入结果数组ret.push_back(tmp);}return ret;}};

二叉树最大宽度

题目：二叉树最大宽度

思路
对于数组存储的二叉树，我们知道

• 父亲节点下标为i（从一开始）。则，
• 左孩子下标为2 * i
• 左孩子下标为2 * i + 1

如果二叉树非常不平衡，节点全部在右侧，空节点也进行插入操作去计算的话，空间是远远不够的

• 我们可以通过计算每层插入节点的头和尾下标差值，并使用vector来模拟队列操作
• 每次都覆盖前一层，以防超出内存
• 计算差值，使用无符号整型，避免数据溢出

• 定义一个队列 vector<pair<TreeNode*, unsigned int>> q；// 数组模拟队列，元素包含一个二叉树节点指针和该节点在完全二叉树中的编号
• 将根节点和其对应编号 1 放入队列 q中
• 进入循环，获取当前层数收尾元素，并且更新当前最大宽度
• 创建一个临时队列tmp来更新q

C++代码

/*** 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;}
};

在每个树行中找最大值

题目：在每个树行中找最大值

思路

利用层序遍历，统计每层最大值；

C++代码

/*** 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 n = q.size();int _max = INT_MIN;for(int i = 0; i < n; i++){auto t = q.front();q.pop();_max = max(_max, t->val);if(t->left) q.push(t->left);if(t->right) q.push(t->right);}ret.push_back(_max);}return ret;}
};