当前位置: 首页 > news >正文

BFS算法——广度优先搜索,探索未知的旅程(下)

文章目录

  • 前言
  • 一. N叉树的层序遍历
    • 1.1 题目链接:https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/
    • 1.2 题目分析:
    • 1.3 思路讲解:
    • 1.4 代码实现:
  • 二. 二叉树的锯齿形层序遍历
    • 2.1 题目链接:https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
    • 2.2 题目分析:
    • 2.3 思路讲解:
    • 2.4 代码实现:
  • 三. 二叉树最大宽度
    • 3.1 题目链接:https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
    • 3.2 题目分析:
    • 3.3 思路讲解:
    • 3.4 代码实现:
  • 四. 在每个树行中找最大值
    • 4.1 题目链接:https://leetcode.cn/problems/find-largest-value-in-each-tree-row/descri
    • 4.2 题目分析:
    • 4.3 思路讲解:
    • 4.4 代码实现:
  • 小结

在这里插入图片描述

前言

上篇我们介绍了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算法的介绍就暂告段落啦,希望能对大家的学习产生帮助,欢迎各位佬前来支持斧正!!!

在这里插入图片描述

相关文章:

BFS算法——广度优先搜索,探索未知的旅程(下)

文章目录 前言一. N叉树的层序遍历1.1 题目链接&#xff1a;https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/1.2 题目分析&#xff1a;1.3 思路讲解&#xff1a;1.4 代码实现&#xff1a; 二. 二叉树的锯齿形层序遍历2.1 题目链接&#xff1a;htt…...

Python分享20个Excel自动化脚本

在数据处理和分析的过程中&#xff0c;Excel文件是我们日常工作中常见的格式。通过Python&#xff0c;我们可以实现对Excel文件的各种自动化操作&#xff0c;提高工作效率。 本文将分享20个实用的Excel自动化脚本&#xff0c;以帮助新手小白更轻松地掌握这些技能。 1. Excel单…...

pytest+request+yaml+allure 接口自动化测试全解析[手动写的跟AI的对比]

我手动写的:Python3:pytest+request+yaml+allure接口自动化测试_request+pytest+yaml-CSDN博客 AI写的:pytest+request+yaml+allure 接口自动化测试全解析 在当今的软件开发流程中,接口自动化测试扮演着至关重要的角色。它不仅能够提高测试效率,确保接口的稳定性和正确性…...

深入解析 FFmpeg 的 AAC 编解码过程

深入解析 FFmpeg 的 AAC 编解码过程 —— 技术详解与代码实现 AAC(Advanced Audio Coding) 是一种高效的有损音频压缩格式,因其高压缩效率和良好的音质而被广泛应用于流媒体、广播和音频存储等领域。FFmpeg 是一个强大的多媒体处理工具,支持 AAC 的编码和解码。本文将详细…...

嵌入式硬件篇---OpenMV串口通信json字符串

文章目录 前言第一部分:Json字符串通信协议优点缺点 Json优点缺点编码与解码 第二部分:UART串口通信UART常用函数注意 总结 前言 以上就是今天要讲的内容&#xff0c;本文简单介绍了Json字符串、UART串口通信。 第一部分:Json字符串 通信协议 在传统的单片机应用中&#xff…...

Python基于Django的课堂投票系统的设计与实现【附源码】

博主介绍&#xff1a;✌Java老徐、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&…...

蓝桥杯 Java 之输入输出

一、输入输出方式&#xff1a;Scanner vs BufferedReader Scanner类 简介&#xff1a;Scanner 是 Java 中一个非常方便的用于读取用户输入的类&#xff0c;它可以从多种输入源&#xff08;如标准输入、文件等&#xff09;读取基本数据类型和字符串。 1. Scanner的细节与使用…...

Kubernetes是什么?为什么它是云原生的基石

从“手工时代”到“自动化工厂” 想象一下&#xff0c;你正在经营一家工厂。在传统模式下&#xff0c;每个工人&#xff08;服务器&#xff09;需要手动组装产品&#xff08;应用&#xff09;&#xff0c;效率低下且容易出错。而Kubernetes&#xff08;k8s&#xff09;就像一个…...

@emotion/styled / styled-components创建带有样式的 React 组件

一、安装依赖 npm install emotion/styled styled-components 二、使用 import styled from emotion/styled; import styled from styled-components;// 创建一个带样式的按钮 const StyledButton styled.buttonbackground-color: #4caf50;color: white;padding: 10px 20px…...

Android 常用命令和工具解析之Battery Historian

Batterystats是包含在 Android 框架中的一种工具&#xff0c;用于收集设备上的电池数据。您可以使用adb bugreport命令抓取日志&#xff0c;将收集的电池数据转储到开发机器&#xff0c;并生成可使用 Battery Historian 分析的报告。Battery Historian 会将报告从 Batterystats…...

家用报警器的UML 设计及其在C++和VxWorks 上的实现01

M.W.Richardson 著&#xff0c;liuweiw 译 论文描述了如何运用 UML&#xff08;统一建模语言&#xff09;设计一个简单的家用报警器&#xff0c;并实现到 VxWorks 操作系统上。本文分两个部分&#xff0c;第一部分描述了如何用 UML 设计和验证家用报警器的模型&#xff0c;以使…...

k8s常见面试题2

k8s常见面试题2 安全与权限RBAC配置如何保护 Kubernetes 集群的 API Server&#xff1f;如何管理集群中的敏感信息&#xff08;如密码、密钥&#xff09;&#xff1f;如何限制容器的权限&#xff08;如使用 SecurityContext&#xff09;&#xff1f;如何防止容器逃逸&#xff0…...

CSS 伪类(Pseudo-classes)的详细介绍

CSS 伪类详解与示例 在日常的前端开发中&#xff0c;CSS 伪类可以帮助我们非常精准地选择元素或其特定状态&#xff0c;从而达到丰富页面表现的目的。本文将详细介绍以下伪类的使用&#xff1a; 表单相关伪类 :checked、:disabled、:enabled、:in-range、:invalid、:optional、…...

将Deepseek接入pycharm 进行AI编程

目录 专栏导读1、进入Deepseek开放平台创建 API key 2、调用 API代码 3、成功4、补充说明多轮对话 总结 专栏导读 &#x1f338; 欢迎来到Python办公自动化专栏—Python处理办公问题&#xff0c;解放您的双手 &#x1f3f3;️‍&#x1f308; 博客主页&#xff1a;请点击——…...

【Ollama】一、介绍

介绍 Ollama 是一个开源项目&#xff0c;专注于提供本地化的大型语言模型&#xff08;LLM&#xff09;部署和运行解决方案。它允许用户在本地环境中轻松运行和微调各种开源语言模型&#xff08;如 LLaMA、Falcon 等&#xff09;&#xff0c;而无需依赖云服务或高性能 GPU。Oll…...

ASP.NET Core JWT

目录 Session的缺点 JWT&#xff08;Json Web Token&#xff09; 优点&#xff1a; 登录流程 JWT的基本使用 生成JWT 解码JWT 用JwtSecurityTokenHandler对JWT解码 注意 Session的缺点 对于分布式集群环境&#xff0c;Session数据保存在服务器内存中就不合适了&#…...

查询引擎:它们是什么以及为什么重要

了解查询引擎、它们的优势以及如何简化现代应用程序的数据管理。查询引擎是高效处理和检索数据的强大工具&#xff0c;但并非所有查询引擎都能满足现代应用程序对速度和实时性的需求。在本文中&#xff0c;我们将解析查询引擎的定义、主要优势以及它们如何用于实时数据和AI应用…...

03/29 使用 海康SDK 对接时使用的 MysqlUtils

前言 最近朋友的需求, 是需要使用 海康sdk 连接海康设备, 进行数据的获取, 比如 进出车辆, 进出人员 这一部分是 资源比较贫瘠时的一个 Mysql 工具类 测试用例 public class MysqlUtils {public static String MYSQL_HOST "192.168.31.9";public static int MY…...

2025.2.7 Python开发岗面试复盘

2025.2.7 Python开发岗面试复盘 问题: 是否了解过其他语言? 了解过Java、JavaScript、C等语言,但主要技术栈是Python。 Python跟Java的区别? Python是解释型语言,Java是编译型语言 Python动态类型,Java静态类型 Python简洁易读,Java相对严谨复杂 Python GIL限制并发,Java并…...

一个sql只能有一个order by

ORDER BY 子句在 SQL 中只能出现一次&#xff0c;静态部分和动态部分只能写一个 ORDER BY...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...