BFS算法——广度优先搜索，探索未知的旅程（下）

前言

上篇我们介绍了BFS算法的思想和代码实现，本篇我们将结合具体题目，进一步深化对于BFS算法的理解运用。

一. N叉树的层序遍历

1.1 题目链接：https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/

1.2 题目分析：

• 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
• 与二叉树不同，该树可能有多个孩子节点，在层序遍历令下一层节点入队列时需要注意遍历方式

1.3 思路讲解：

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

1.4 代码实现：

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> temp;//存储该层节点的值for(int i=0;i<sz;i++){auto t=q.front();q.pop();temp.push_back(t->val);//下一层节点入队列for(auto& child:t->children){q.push(child);}}ret.push_back(temp);//更新}return ret;}
};

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

2.1 题目链接：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/

2.2 题目分析：

• 要求进行二叉树的层序遍历
• 遍历时按照奇数层从左到右，偶数层从右到左的方式进行遍历

2.3 思路讲解：

本题的核心还是在于二叉树的层序遍历，我们可以通过level来记录层数，判断遍历方向。

2.4 代码实现：

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ret;//返回数组queue<TreeNode*> q;//队列if(root==nullptr){return ret;}//处理特殊情况q.push(root);int level=1;//记录层数while(q.size()){int sz=q.size();//该层节点个数vector<int> temp;//存储该层节点的值for(int i=0;i<sz;i++){auto t=q.front();q.pop();temp.push_back(t->val);//下一层节点入队列if(t->left) q.push(t->left);if(t->right) q.push(t->right);}if(level%2==0){reverse(temp.begin(),temp.end());}//处理偶数层情况ret.push_back(temp);level++;//更新层数}return ret;}
};

三. 二叉树最大宽度

3.1 题目链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/description/

3.2 题目分析:

• 给定二叉树，求其最大宽度
• 其中宽度是指一层里面起始节点到最终节点的节点数，空节点也算一个节点
• 

3.3 思路讲解：

思路一：层序遍历计算节点个数（会超出内存限制）

• 利用层序遍历的思想，一层层计录节点个数，将空节点也包含在内
• 但在遇到极端单链情况时，节点数目会异常庞大，导致超出内存限制

思路二：利用二叉树的顺序存储，计算左右下标

• 依旧是利⽤层序遍历，但是这⼀次队列⾥⾯不单单存结点信息，并且还存储当前结点如果在数组中存储所对应的下标（在我们学习数据结构 - 堆的时候，计算左右孩⼦的⽅式）。

• 这样我们计算每⼀层宽度的时候，⽆需考虑空节点，只需将当层结点的左右结点的下标相减再加1即可。

但是，这⾥有个细节问题：如果⼆叉树的层数⾮常恐怖的话，我们任何⼀种数据类型都不能存下下标的值。但是没有问题，因为
• 我们数据的存储是⼀个环形的结构；
• 并且题⽬说明，数据的范围在 int 这个类型的最⼤值的范围之内，因此不会超出⼀圈；
• 因此，如果是求差值的话，我们⽆需考虑溢出的情况。

此处下标的记录需要用unsigned int！！！

3.4 代码实现：

/*** 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;//用数组模拟队列if(root==nullptr){return 0;}//处理特殊情况q.push_back({root,1});unsigned int width=1;//宽度while(q.size()){//先更新本层宽度auto [x1,y1]=q[0];auto [x2,y2]=q.back();width=max(width,y2-y1+1);vector<pair<TreeNode*,unsigned int>> temp;//存储数组for(auto& [x,y]:q){//左右节点入队列if(x->left){temp.push_back({x->left,2*y});}if(x->right){temp.push_back({x->right,2*y+1});}}q=temp;//更新队列}return width;}
};

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

4.1 题目链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/descri

4.2 题目分析：

• 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

4.3 思路讲解：

本题核心仍然为层序遍历，只需记录每一层的最大值即可

4.4 代码实现：

class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> ret;//返回数组queue<TreeNode*> q;if(root==nullptr){return ret;}//处理特殊情况q.push(root);while(q.size()){int sz=q.size();//本层节点数int temp=INT_MIN;//记录本层最大值for(int i=0;i<sz;i++){auto t=q.front();q.pop();temp=max(temp,t->val);//下一层入队列if(t->left){q.push(t->left);}if(t->right){q.push(t->right);}}ret.push_back(temp);}return ret;}
};

小结

在BFS的世界里，我们能够感受到一种近乎哲学的智慧，它并不急功近利，而是循序渐进，逐步展开。每一层的遍历，每一个节点的访问，都是对“问题解答”的一步步接近。而当问题的答案最终浮现，我们也能够感叹，原来最简单的思路，往往是最伟大的。

本篇关于BFS算法的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！