算法沉淀——队列+宽度优先搜索(BFS)(leetcode真题剖析)

算法沉淀——队列+宽度优先搜索(BFS)
- 01.N 叉树的层序遍历
- 02.二叉树的锯齿形层序遍历
- 03.二叉树最大宽度
- 04.在每个树行中找最大值
队列 + 宽度优先搜索算法(Queue + BFS)是一种常用于图的遍历的算法,特别适用于求解最短路径或最少步数等问题。该算法通常用于在图中寻找从起点到目标点的最短路径。
基本思想:
- 初始化队列: 将起始节点放入队列中。
- BFS遍历: 从队列中取出一个节点,遍历与该节点相邻且未访问过的节点,将其加入队列。
- 标记已访问: 标记已访问的节点,避免重复访问。
- 重复步骤2和3: 直到队列为空。
这个算法适用于无权图的最短路径问题。在搜索的过程中,每一层级的节点都会被依次访问,直到找到目标节点。
具体步骤:
- 将起始节点加入队列。
- 进行循环直到队列为空: a. 从队列中取出一个节点。 b. 如果该节点是目标节点,返回结果。 c. 否则,将与该节点相邻且未访问过的节点加入队列,并标记为已访问。
这种算法适用于许多场景,例如迷宫问题、游戏中的寻路问题、网络路由算法、树问题等。在这些问题中,它能够有效地找到最短路径或最优解。
01.N 叉树的层序遍历
题目链接:https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。
树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。
示例 1:

输入:root = [1,null,3,2,4,null,5,6]
输出:[[1],[3,2,4],[5,6]]
示例 2:

输入: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]]
提示:
- 树的高度不会超过
1000 - 树的节点总数在
[0, 10^4]之间
思路
在树的层序遍历中经常要使用到的就是队列和宽度优先搜索算法,这是一道经典的队列和宽度优先搜索算法模板题
-
初始化一个空的二维向量
ret用于存储层次遍历的结果。 -
如果根节点
root为空,直接返回空向量ret。 -
创建一个队列
q并将根节点入队。 -
进入主循环,该循环将处理每一层的节点: a. 获取当前队列的大小,即当前层的节点数。 b. 创建一个临时向量
tmp用于存储当前层的节点值。 c. 对于当前层的每个节点:
- 出队一个节点
t。 - 将节点值
t->val存入tmp。 - 将该节点的所有子节点入队,如果子节点非空。 d. 将
tmp存入ret。
- 出队一个节点
-
返回最终的层次遍历结果
ret。
代码
/*
// 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) 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();tmp.push_back(t->val);for(Node* x:t->children) if(x) q.push(x);q.pop();}ret.push_back(tmp);}return ret;}
};
02.二叉树的锯齿形层序遍历
题目链接:https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
给你二叉树的根节点 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
思路
这一题我们仔细理解题意,我们不难发现这题和上一题的区别就是,在偶数行时需要逆序,所以我们只要再添加一个偶数列逆序的操作即可,其余同上。
- 引入一个标志变量
flag,用于标识当前层次是奇数层还是偶数层。初始化为0。 - 初始化一个队列
q用于层次遍历,以及一个二维向量ret用于存储结果。 - 如果根节点
root为空,直接返回空向量ret。 - 将根节点入队。
- 进入主循环,该循环处理每一层的节点: a. 获取当前队列的大小,即当前层的节点数,用
s表示。 b. 递增flag。 c. 创建一个临时向量tmp用于存储当前层的节点值。 d. 对于当前层的每个节点:- 出队一个节点
t。 - 将节点值
t->val存入tmp。 - 如果节点
t的左子节点非空,将其入队。 - 如果节点
t的右子节点非空,将其入队。 e. 如果flag为偶数,反转tmp中的元素顺序。 f. 将tmp存入ret。
- 出队一个节点
- 返回最终的层次遍历结果
ret。
代码
/*** 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) {queue<TreeNode*> q;vector<vector<int>> ret;if(!root) return ret;q.push(root);int flag=0;while(q.size()){int s=q.size();flag++;vector<int> tmp;for(int i=0;i<s;++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;}
};
03.二叉树最大宽度
题目链接:https://leetcode.cn/problems/maximum-width-of-binary-tree
给你一棵二叉树的根节点 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
思路
这道题最大的坑点在于如果二叉树极度不平衡,若使用模拟的方式,空节点也进行插入操作去计算的话,空间是远远不够的,所以这里我们不能像前面两题这样操作,我们可以通过计算每层插入节点的头和尾下标差值,并使用vector来模拟队列操作,每次都覆盖前一层,以防超出内存,还有计算差值,我们使用无符号整型,这样我们可以避免数据溢出带来的计算错误的值
- 定义一个队列
q,其中每个元素是一个pair,包含一个二叉树节点指针和该节点在完全二叉树中的编号。 - 将根节点和其对应编号 1 放入队列
q中。 - 初始化一个变量
ret用于存储最大宽度。 - 进入主循环,该循环用于遍历二叉树的每一层。 a. 获取当前队列的首尾元素,即队列中最左边和最右边的节点及其编号。 b. 计算当前层的宽度,即
y2 - y1 + 1,其中y1是最左边节点的编号,y2是最右边节点的编号。 c. 更新ret,取ret和当前层宽度的较大值。 d. 创建一个临时队列tmp。 e. 遍历队列q中的每个节点:- 如果节点有左子节点,将左子节点及其编号(编号乘以 2)加入
tmp。 - 如果节点有右子节点,将右子节点及其编号(编号乘以 2 加 1)加入
tmp。 f. 将tmp赋值给队列q。
- 如果节点有左子节点,将左子节点及其编号(编号乘以 2)加入
- 返回最终的宽度
ret。
代码
/*** 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;}
};
04.在每个树行中找最大值
题目链接:https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。
示例1:

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2:
输入: root = [1,2,3]
输出: [1,3]
提示:
- 二叉树的节点个数的范围是
[0,104] -231 <= Node.val <= 231 - 1
思路
根据前面几个题型,我们不难想到,无非就是在层序遍历的基础上增加一个每层的最大值计算,在之前的基础上增加条件即可。
- 定义一个队列
q,其中每个元素是二叉树节点指针。 - 将根节点放入队列
q中。 - 初始化一个空的数组
ret,用于存储每一层的最大值。 - 进入主循环,该循环用于遍历二叉树的每一层。 a. 初始化一个变量
m为INT_MIN,用于记录当前层的最大值。 b. 获取当前队列的大小(即当前层的节点数)。 c. 遍历当前层的每个节点:- 弹出队列的首元素,即最左边的节点。
- 更新
m,取m和当前节点值的较大值。 - 如果节点有左子节点,将左子节点加入队列
q。 - 如果节点有右子节点,将右子节点加入队列
q。 d. 将m添加到数组ret中。
- 返回最终的数组
ret,其中包含了每一层的最大值。
代码
/*** 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*> q;vector<int> ret;if(!root) return ret;q.push(root);while(q.size()){int m=INT_MIN;int n=q.size();for(int i=0;i<n;++i){auto t=q.front();q.pop();m=max(m,t->val);if(t->left) q.push(t->left);if(t->right) q.push(t->right);}ret.push_back(m);}return ret;}
};
相关文章:
算法沉淀——队列+宽度优先搜索(BFS)(leetcode真题剖析)
算法沉淀——队列宽度优先搜索(BFS) 01.N 叉树的层序遍历02.二叉树的锯齿形层序遍历03.二叉树最大宽度04.在每个树行中找最大值 队列 宽度优先搜索算法(Queue BFS)是一种常用于图的遍历的算法,特别适用于求解最短路径…...
编辑器的新选择(基本不用配置)
Cline 不用看网上那些教程Cline几乎不用配置。 点击设置直接选择Chinese, C直接在选择就行了。 Cline是一个很好的编辑器,有很多懒人必备的功能。 Lightly 这是一个根本不用配置的C编辑器。 旁边有目录,而且配色也很好,语言标准可以自己…...
算法沉淀——栈(leetcode真题剖析)
算法沉淀——栈 01.删除字符串中的所有相邻重复项02.比较含退格的字符串03.基本计算器 II04.字符串解码05.验证栈序列 栈(Stack)是一种基于先进后出(Last In, First Out,LIFO)原则的数据结构。栈具有两个主要的操作&am…...
耳机壳UV树脂制作私模定制耳塞需要注意什么问题?
制作私模定制耳塞需要注意以下问题: 耳模制作:获取准确的耳模是制作私模定制耳塞的关键步骤。需要使用合适的材料和方法,确保耳模的准确性和稳定性。材料选择:选择合适的UV树脂和其它相关材料,确保它们的质量和性能符…...
easyx搭建项目-永七大作战(割草游戏)
永七大作战 游戏介绍: 永七大作战 游戏代码链接:永七大作战 提取码:ABCD 不想水文了,直接献出源码,表示我的诚意...
nginx命名location跳转的模块上下文继承
目录 1. 缘起2. 解决方案2.1 保留指定模块的上下文信息2.2 获取指定模块的上下文信息2.3 设置指定模块的上下文信息2.4 设置模块上下文是否需要继承标记2.5 对openrety lua代码的支持 1. 缘起 nginx提供了非常棒的功能,命名location,如文章nginx的locati…...
洛谷 P2678 [NOIP2015 提高组] 跳石头 (Java)
洛谷 P2678 [NOIP2015 提高组] 跳石头 (Java) 传送门:P2678 [NOIP2015 提高组] 跳石头 题目: [NOIP2015 提高组] 跳石头 题目背景 NOIP2015 Day2T1 题目描述 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行&…...
第2讲投票系统后端架构搭建
创建项目时,随机选择一个,后面会生成配置properties文件 生成文件 maven-3.3.3 设置阿里云镜像 <?xml version"1.0" encoding"UTF-8"?><!-- Licensed to the Apache Software Foundation (ASF) under one or more cont…...
Flask 入门7:使用 Flask-Moment 本地化日期和时间
如果Web应用的用户来自世界各地,那么处理日期和时间可不是一个简单的任务。服务器需要统一时间单位,这和用户所在的地理位置无关,所以一般使用协调世界时(UTC)。不过用户看到 UTC 格式的时间会感到困惑,他们…...
FileZilla Server 1.8.1内网搭建
配置环境服务器服务器下载服务器配置服务器配置 Server - ConfigureServer Listeners - Port 协议设置 Protocols settingsFTP and FTP over TLS(FTPS) Rights management(权利管理)Users(用户) 客户端建立连接 配置环境 服务器处于局域网内: 客户端 < -访问- > 公网 &l…...
C++LNK1207中的 PDB 格式不兼容;请删除并重新生成
在打开别人发的C文件时,可能出现该报错 解决办法 打开资源管理器,找到原来的路径 进入Debug, 找到对应的PDB文件删除即可。...
小白学习Halcon100例:如何利用动态阈值分割图像进行PCB印刷缺陷检测?
文章目录 *读入图片*关闭所有窗口*获取图片尺寸*根据图片尺寸打开一个窗口*在窗口中显示图片* 缺陷检测开始 ...*1.开运算 使用选定的遮罩执行灰度值开运算。*2.闭运算 使用选定的遮罩执行灰度值关闭运算*3.动态阈值分割 使用局部阈值分割图像显示结果*显示原图*设置颜色为红色…...
车载诊断协议DoIP系列 —— 车载以太网诊断需求规范(网关、路由)
车载诊断协议DoIP系列 —— 车载以太网诊断需求规范(网关、路由) 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师(Wechat:gongkenan2013)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 本就是小人物,输了就是输了,不要在意别人怎么看自…...
面试官:介绍一下MVC框架
前言 大家好,我是chowley,MVC相信大家都听说过,今天我就记录一下我心中的MVC框架 MVC(Model-View-Controller)是一种软件设计模式,用于将应用程序分为三个核心部分:模型(Model&…...
C++ new 和 malloc 的区别?
相关系列文章 C内存分配策略-CSDN博客 目录 1.引言 2.区别 2.1.申请的内存分配区域 2.2.类型安全和自动大小计算 2.3.构造函数和析构函数的调用 2.4.异常处理 2.5.配对简便性 2.6.new 的重载 2.7.关键字和操作符 3.总结 1.引言 new 和 delete 在 C 中被引入…...
腾讯云4核8G服务器多少钱?
腾讯云4核8G服务器多少钱?轻量应用服务器4核8G12M带宽一年446元、646元15个月,云服务器CVM标准型S5实例4核8G配置价格15个月1437.3元,5年6490.44元,标准型SA2服务器1444.8元一年,在txy.wiki可以查询详细配置和精准报价…...
独孤思维:看到副业坚持4年,我震惊了
01 新人写作,不要写纯理论的东西,也不要写自我高潮的内容。 都写点接地气,多实操的内容。 比如,独孤现在每一篇短文写作,都会引入一个案例。 这样,对于很多读者来说,更好理解,能…...
kali无线渗透之wps加密模式和破解12
WPS(Wi-Fi Protected Setup,Wi-Fi保护设置)是由Wi-Fi联盟推出的全新Wi-Fi安全防护设定标准。该标准推出的主要原因是为了解决长久以来无线网络加密认证设定的步骤过于繁杂之弊病,使用者往往会因为步骤太过麻烦,以致干脆不做任何加密安全设定&…...
gorm day8
gorm day8 gorm Has Many关系gorm Many To Many关系 gorm Has Many关系 Has Many 在GORM(Go的一个对象关系映射库)中,“Has Many” 关系表示一个实体与另一个实体之间的一对多关系。这意味着一个实体(我们称之为"父"…...
【计算机网络】【练习题及解答】【新加坡南洋理工大学】【Computer Control Network】【Exercise Solution】
说明: 个人资料,仅供学习使用,版权归校方所有。 一、题目描述 该问题接上期博文【练习题及解答】,描述网络通信中的链路效率(Link Efficiency),即Link Utilization的计算。(此处认…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...
0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化
是不是受够了安装了oracle database之后sqlplus的简陋,无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话,配置.bahs_profile后也能解决上下翻页这些,但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可,…...
图解JavaScript原型:原型链及其分析 | JavaScript图解
忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...
一些实用的chrome扩展0x01
简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序,无论是测试应用程序、搜寻漏洞还是收集情报,它们都能提升工作流程。 FoxyProxy 代理管理工具,此扩展简化了使用代理(如 Burp…...
DeepSeek越强,Kimi越慌?
被DeepSeek吊打的Kimi,还有多少人在用? 去年,月之暗面创始人杨植麟别提有多风光了。90后清华学霸,国产大模型六小虎之一,手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水,单月光是投流就花费2个亿。 疯…...
从零手写Java版本的LSM Tree (一):LSM Tree 概述
🔥 推荐一个高质量的Java LSM Tree开源项目! https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree,专为高并发写入场景设计。 核心亮点: ⚡ 极致性能:写入速度超…...
