深度解析算法之队列+宽搜（BFS）
在做这里的一些题的时候，建议将递归、搜索与回溯相关的题目看看
71.N 叉树的层序遍历
题目链接 给定一个 N 叉树，返回其节点值的_层序遍历_。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
image.png
输入： root = [1,null,3,2,4,null,5,6] 输出： [[1],[3,2,4],[5,6] ]
示例 2：
image.png
输入： root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14] ]
将每一层的节点的数据放到数组中进行返回操作
这里的话我们是需要借助队列这个数据结构
BFS就是层序遍历
先将根节点放到队列中，然后获取队列头元素的孩子放到队列中，然后将这个根节点删除，然后按照这样依次将头元素获取然后删除操作
我们在每次引入根节点之前需要进行统计当前队列中存在多少个节点，这个统计的结果就是我们每一层的节点的个数，
/*
// 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 sz=q.size();//统计当前队列中的元素个数，就是我们这一层的节点数
vector<int>tmp;//统计本层的节点
for(int i=0;i<sz;i++)//我们只需要执行sz次，将队列中的孩子出队
{
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;
}
};先将根节点入队列，然后统计这一层的节点的个数sz 然后循环sz次，将我们的这个节点删除，在删除之前，我们是需要将我们的根节点的孩子引入到队列中去，只要不是空节点，都入队列
引入根节点，引入孩子，删除根节点，依次循环操作
72.二叉树的锯齿形层序遍历
题目链接
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入： root = [3,9,20,null,null,15,7] 输出： [[3],[20,9],[15,7] ]
示例 2：
输入： root = [1] 输出：[[1]]
示例 3：
输入： root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -100 <= Node.val <= 100
image.png
在层序遍历的基础上我们奇数行不变，偶数行的话，我们进行一个逆置，然后放到ret中去
增加一个标志位，让偶数行的信息逆序即可
image.png
/**
* 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==nullptr)return ret;//如果是根节点是空的话 ，我们直接返回就行了
queue<TreeNode*>q;
q.push(root);//先让根节点入队列、、
int level=1;
while(q.size())
{
int sz=q.size();
vector<int>tmp;//存储结果
for(int i=0;i<sz;i++)
{
auto t=q.front();//获取头节点信息
q.pop();//头删
tmp.push_back(t->val);
if(t->left)q.push(t->left);//如果t的左节点不为空的话，那么我们就放到队列来
if(t->right)q.push(t->right);
}
//那么循环结束了，我们将将这么一层的信息统计到了tmp中去了
//判断是否逆序
if(level%2==0) reverse(tmp.begin(),tmp.end());//如果是偶数层的话，那么我们就将tmp中存的结果进行逆置操作
ret.push_back(tmp);//将tmp存到结果中去
level++;
}
return ret;
}
};在层序遍历的基础上，判断我们的偶数层，如果是偶数层的话，我们就进行逆序操作，奇数的话就不变
73.二叉树最大宽度
题目链接
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1：
输入： root = [1,3,2,5,3,null,9] 输出： 4 **解释：**最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
示例 2：
输入： root = [1,3,2,5,null,null,9,6,null,7] 输出： 7 解释： 最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
示例 3：
输入： root = [1,3,2,5] 输出： 2 解释： 最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
提示：
- 树中节点的数目范围是
[1, 3000] -100 <= Node.val <= 100
image.png
利用数组存储二叉树的方式，给节点编号 给每个节点进行一个编号的操作，每个节点进队就给节点绑定一个号码 那么我们就不需要考虑空节点了
下标有可能溢出，深度太深了，超出int
当我们相减之后，即是溢出，结果也是正确的 我们C++这里使用无符号的int进行下标的存储操作
/**
* 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];//队头元素我们就使用q[o]获取到了，这个就是键值对里面的first
auto&[x2,y2]=q.back();//队尾的数据
ret=max(ret,y2-y1+1);//更新我们的此时树的宽度
//让下一层进队
vector<pair<TreeNode*,unsigned int>>tmp;//让下一层进入到这个队列
for(auto&[x,y]:q)//遍历我们的q这个队列
{
//这里的话我们是使用花括号将键值对的信息存起来然后插入到tmp中去
if(x->left)tmp.push_back({x->left,y*2});//如果左孩子存在的话，那么我们就让节点入队，左孩子的下标是y*2
if(x->right)tmp.push_back({x->right,y*2+1});
}
//当在整个for循环结束后，我们就将我们的下一层节点进入到队列里面去了
q=tmp;//直接进行数据覆盖操作
}
return ret;
}
};使用数组模拟队列，将我们的节点和他们对应的下标存放起来就行了 每次遍历一层就将队头元素和队尾元素的下标拿出来进行相减，进行最大宽度的比较操作
pair就是一个键值对的类型
一开始我们将根节点和下标进行入队，然后后面就能根据判断进行左右节点的入队操作了
74.在每个树行中找最大值
题目链接
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
示例2：
输入: root = [1,2,3] 输出: [1,3]
思想：在层序遍历的基础之上，维护一个变量，记录这一层的最大值就行了
/**
* 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 sz=q.size();//记录这层有多少个节点
int tmp=INT_MIN;//让所有值和这个无穷下做比较就行了，来标记我们的最大值
for(int i=0;i<sz;i++)
{
auto t=q.front();//获取队头元素
q.pop();//删除队头元素
tmp=max(tmp,t->val);//更新我们的最大值
if(t->left)q.push(t->left);//左孩子存在的话就将左孩子存进去
if(t->right)q.push(t->right );
}
//循环结束之后，我们就计算出来了这一层的最大值，并且将下一层放到队列中去了
ret.push_back(tmp);
}
return ret;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-07-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号