34二叉树-BFS和DFS求树的深度
目录
LeetCode之路——104. 二叉树的最大深度
分析
解法一:广度优先遍历
解法二:深度优先遍历
总结
深度优先搜索 (DFS)
广度优先搜索 (BFS

LeetCode之路——104. 二叉树的最大深度
给定一个二叉树 root ,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1:

输入:root = [3,9,20,null,null,15,7] 输出:3
示例 2:
输入:root = [1,null,2] 输出:2
提示:
-
树中节点的数量在
[0, 104]区间内。 -
-100 <= Node.val <= 100
分析
解法一:广度优先遍历
class Solution {public int maxDepth(TreeNode root) {if(root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);int deep = 0;while(!queue.isEmpty()){int len = queue.size();while(len > 0){TreeNode curr = queue.poll();if(curr.left != null) queue.offer(curr.left);if(curr.right != null) queue.offer(curr.right);len--;}deep++;}return deep;}
}
-
时间复杂度:O(n)
-
空间复杂度:O(n)
解法二:深度优先遍历
class Solution {public int maxDepth(TreeNode root) {if(root == null) {return 0;} else {int leftDeep = maxDepth(root.left);int rightDeep = maxDepth(root.right);return Math.max(leftDeep, rightDeep) + 1;} }
}
-
时间复杂度:O(n)
-
空间复杂度:O(deep)
总结
深度优先搜索 (DFS)
-
遍历顺序:以深度为优先,从根节点开始,沿着一条路径尽可能深入,然后回溯并继续深入到下一个分支。
-
数据结构:通常使用递归或显式的栈数据结构来实现。递归调用构成了一个栈,用于跟踪路径。
-
适用性:适用于寻找路径、拓扑排序、连通性分析、深度分析等问题。通常用于在图中找到一条路径或寻找目标节点。
-
空间复杂度:通常具有较低的空间复杂度,尤其在递归版本中。但在非平衡树中,空间复杂度可能较高。
-
实现难度:通常更容易实现,特别是使用递归。递归版本的DFS代码通常较短。
广度优先搜索 (BFS
-
遍历顺序:以广度为优先,从起始节点开始,首先访问所有与起始节点直接相邻的节点,然后逐层向外扩展,依次访问更远的节点。
-
数据结构:通常使用队列数据结构来实现。队列用于存储待访问的节点,确保先访问当前层的节点,然后再访访问下一层的节点。
-
适用性:适用于寻找最短路径、最短距离、广度分析等问题。通常用于寻找最短路径或在树/图中查找目标节点。
-
空间复杂度:通常具有较高的空间复杂度,因为它需要存储待访问节点的队列。在完全图中,空间复杂度可能最高。
-
实现难度:相对较复杂,需要维护一个队列,处理节点的层级等。
选择DFS还是BFS取决于问题的性质。如果要找到最短路径,BFS通常更合适。如果要执行深度分析或寻找路径,DFS可能更适合。在某些情况下,它们可以相互转化为其他问题,例如,可以使用DFS来找到所有路径,然后选择其中最短的路径。综合考虑问题的需求和数据结构的特点,选择适当的算法。
相关文章:
34二叉树-BFS和DFS求树的深度
目录 LeetCode之路——104. 二叉树的最大深度 分析 解法一:广度优先遍历 解法二:深度优先遍历 总结 深度优先搜索 (DFS) 广度优先搜索 (BFS LeetCode之路——104. 二叉树的最大深度 给定一个二叉树 root ,返回其最大深度。 二叉树的…...
Android Glide判断图像资源是否缓存onlyRetrieveFromCache,使用缓存数据,Kotlin
Android Glide判断图像资源是否缓存onlyRetrieveFromCache,使用缓存数据,Kotlin import android.graphics.Bitmap import android.os.Bundle import android.util.Log import android.widget.ImageView import androidx.appcompat.app.AppCompatActivity…...
设计模式之创建型模式
创建型模式与对象的创建有关。 创建型模式抽象了对象实例化的过程,这些设计模式提供了一种在创建对象的同时隐藏创建逻辑的方式,而不是使用 new 运算符直接实例化对象。创建型模式有以下 工厂模式(Factory Method) 意图…...
使用jdbc技术连接数据库
连接数据库 <dependencies><dependency><groupId>mysql</groupId><artifactId>mysql-connector-java</artifactId><version>8.0.28</version><scope>compile</scope></dependency> </dependencies> g…...
OpenLayers入门,快速搭建vue+OpenLayers地图脚手架项目
专栏目录: OpenLayers入门教程汇总目录 前言 本章针对Vue初学者,对Vue不熟悉,甚至还不会Vue的入门学生读者。 本章会详细讲解从NodeJS环境到npm环境的各个步骤,再到使用vue-cli脚手架快速生成项目,以及添加OpenLayers地图库依赖,编写简单的xyz高德地图显示页面的完整教…...
完成比写得好更重要,先完成初稿再说
我发现自己有个毛病,总想着满意了才动手。于是,经常做到一半跑去看文献,然后陷入文献中觉得这个比自己好,那个比自己好。于是,暂时中断手边工作,最后进度被推迟,甚至啥也没做出来。 今晚再次听…...
Spring boot 处理复杂json接收,同种类型、不同场景处理
场景: json大体格式一致,但是 ext_info 扩展字段对象,场景不同字段不同根据某字段类型,不同值,对应不同实现的 Component,处理不同场景这里根据 event,来做不同处理 {"data": {"event"…...
排列置换环上构造:1025T3
http://cplusoj.com/d/senior/p/SS231025C 排列构造的新知识:上置换环! 我们发现朴素做法是 n 2 n^2 n2 级别的,但数据范围希望我们是 n 2 2 \frac {n^2}2 2n2 级别的。我们发现我们暴力复制序列显得非常蠢,因为很多序列前后…...
Stable diffusion的一些参数意义及常规设置
在线stabel Diffusion模型 https://huggingface.co/spaces/stabilityai/stable-diffusion 随机种子 seed 如果想要同一个文本提示,生成多次都是同一图像,可以设置一个随机种子,类似于random.seed()的原理,并将生成器传递给管道。…...
成员变量、静态成员变量、局部变量、常量的内存区域
一、Java中没有全局变量的概念,变量分为类的成员变量、静态成员变量和方法中的局部变量 1、局部变量,基本类型的局部变量变量名和值都存放在虚拟机栈中,引用类型的局部变量变量名存放在栈中,而变量指向的对象存放在堆中。记也很好…...
网络协议--IGMP:Internet组管理协议
13.1 引言 12.4节概述了IP多播给出,并介绍了D类IP地址到以太网地址的映射方式。也简要说明了在单个物理网络中的多播过程,但当涉及多个网络并且多播数据必须通过路由器转发时,情况会复杂得多。 本章将介绍用于支持主机和路由器进行多播的In…...
网络安全https
http是明文的,相当于在网上裸奔,引出了https,大多数网站都转为了https,连非法的赌博网站有的都是https的。 1.https的网站是不是必须让用户装数字证书? 答:分两种,一种是单向认证,像…...
xcode Simulator 手动安装
xcode Simulator 手动安装 参考文档 xcode又又又升级了,升级完成之后不下载最新的 iOS 17 Simulator就不能编译运行了,只能静静的等他下载。但是离谱的是这个居然没有断点续下,每次都要重新下载,眼睁睁的看着下载了4个G然后断掉…...
Unity中国、Cocos为OpenHarmony游戏生态插上腾飞的翅膀
2023年是OpenHarmony游戏生态百花齐放的一年!为了扩展OpenHarmony游戏生态,OpenHarmony在基金会成立了游戏SIG小组,游戏SIG小组联合cocos,从cocos2dx入手一周内快速适配了cocos2.2.6的MVP版本,随后又分别适配了cocos2d…...
Monaco Editor编辑器
monaco-editor Monaco Editor 是一个基于浏览器的代码编辑器,由微软开发。它提供了丰富的功能,包括语法高亮、智能代码补全、代码折叠、多光标编辑等。Monaco Editor 是 Visual Studio Code 的核心编辑器,也被广泛用于其他开发工具和在线代码…...
ARM | 传感器必要总线IIC
IIC总线介绍 1.谈谈你对IIC总线理解? 1)IIC总线是串行半双工同步总线,主要用于连接整体电路 2)SCL/SDA作用:IIC是两线制,一根是时钟线SCK,用于控制什么时候进行进行数据传输,时钟信号由主机发出; 另一根是数据线SDA,用于进行数据传输,可以从…...
Mybatis中Resources和ClassLoaderWrapper
ClassLoaderWrapper Resources...
Linux多线程服务端编程:使用muduo C++网络库 学习笔记 第三章 多线程服务器的适用场合与常用编程模型
本文中的多线程服务器指运行在Linux上的独占式网络应用程序。硬件平台为Intel x86-64系列的多核CPU,单路或双路SMP(Symmetric Multi-Processing,对称多处理,它是一种多核处理器架构,其中多个CPU核心共享系统的内存和其…...
windows下使用FFmpeg开源库进行视频编解码完整步聚
最终解码效果: 1.UI设计 2.在控件属性窗口中输入默认值 3.复制已编译FFmpeg库到工程同级目录下 4.在工程引用FFmpeg库及头文件 5.链接指定FFmpeg库 6.使用FFmpeg库 引用头文件 extern "C" { #include "libswscale/swscale.h" #include "libavdevic…...
如何更改eclipse的JDK版本
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 一、有时候导入一些网上的资源需要更换JDK二、使用步骤1. 总结 一、有时候导入一些网上的资源需要更换JDK 具体操作如下 二、使用步骤 1. 在eclipse上方工具栏找…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
