LeetCode-111. 二叉树的最小深度
目录
- 题目分析
- 递归法
题目来源
111. 二叉树的最小深度
题目分析
这道题目容易联想到104题的最大深度,把代码搬过来
class Solution {public int minDepth(TreeNode root) {return dfs(root);}public static int dfs(TreeNode root){if(root == null){return 0;}int left = dfs(root.left);int right = dfs(root.right);return Math.min(left,right)+1;}}

然后仔细读题
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。


为了满足题目需求, 需要额外加上一个条件
if(root.left == null && root.right != null)
if(root.left != null && root.right == null)
递归法
递归三部曲
- 1.确定递归函数的参数和返回值
参数为要传入的二叉树根节点,返回的是int类型的深度。
代码如下:
int dfs(TreeNode root)
- 2.确定终止条件
终止条件也是遇到空节点返回0,表示当前节点的高度为0。
代码如下:
if(root == null){return 0;}
- 3.确定单层递归的逻辑
这块和求最大深度可就不一样了
如果左子树为空,右子树不为空,说明最小深度是 1 + 右子树的深度。
反之,右子树为空,左子树不为空,最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空,返回左右子树深度最小值 + 1 。
int leftDepth = dfs(root.left); // 左int rightDepth = dfs(root.right); // 右// 中// 当一个左子树为空,右不为空,这时并不是最低点 if(root.left == null && root.right != null){ return rightDepth + 1;}// 当一个右子树为空,左不为空,这时并不是最低点if(root.left != null && root.right == null){return leftDepth + 1;}return Math.min(leftDepth,rightDepth)+1;
遍历的顺序为后序(左右中),可以看出:求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
整体递归代码
class Solution {public int minDepth(TreeNode root) {if(root == null){return 0;}return dfs(root);}public static int dfs(TreeNode root){if(root == null){return 0;}int leftDepth = dfs(root.left); // 左int rightDepth = dfs(root.right); // 右// 中// 当一个左子树为空,右不为空,这时并不是最低点 if(root.left == null && root.right != null){ return rightDepth + 1;}// 当一个右子树为空,左不为空,这时并不是最低点if(root.left != null && root.right == null){return leftDepth + 1;}return Math.min(leftDepth,rightDepth)+1;}
}

相关文章:
LeetCode-111. 二叉树的最小深度
目录题目分析递归法题目来源111. 二叉树的最小深度题目分析 这道题目容易联想到104题的最大深度,把代码搬过来 class Solution {public int minDepth(TreeNode root) {return dfs(root);}public static int dfs(TreeNode root){if(root null){return 0;}int left…...
git常用命令
(一)克隆代码(clone):将远程仓库代码克隆到本地仓库 克隆远程仓库某个分支 git clone -b 远程分支名称 https://github.com/master/master.git 本地文件名称 克隆远程仓库默认分支 git clone https://github.com/mas…...
2022年12月电子学会Python等级考试试卷(一级)答案解析
青少年软件编程(Python)等级考试试卷(一级) 一、单选题(共25题,共50分) 1. 关于Python语言的注释,以下选项中描述错误的是?( ) A. Python语言有两种注释方式&…...
大数据未来会如何发展
大数据应用的重要性,自全国提出“数据中国”的概念以来,我们周围默默地在发挥作用的大数据逐渐深入人们的心中,大数据的应用也越来越广泛,具体到金融、汽车、餐饮、电信、能源、体育和娱乐等领域 为什么大数据技术那么火…...
2022黑马Redis跟学笔记.基础篇(一)
2022黑马Redis跟学笔记.基础篇 一1.Redis入门1.1.认识NoSQL1.1.1.结构化与非结构化1.1.2.关联和非关联1.1.3.查询方式1.1.4.事务1.1.5.总结1.2.认识Redis1.3.安装Redis步骤一:安装Redis依赖步骤二:上传安装包并解压步骤三:启动(1).默认启动(2…...
【Spring(十一)】万字带你深入学习面向切面编程AOP
文章目录前言AOP简介AOP入门案例AOP工作流程AOP切入点表达式AOP通知类型AOP通知获取数据总结前言 今天我们来学习AOP,在最初我们学习Spring时说过Spring的两大特征,一个是IOC,一个是AOP,我们现在要学习的就是这个AOP。 AOP简介 AOP:面向切面编程,一种编程范式&#…...
基于Java+SpringBoot+Vue+uniapp前后端分离图书阅读系统设计与实现
博主介绍:✌全网粉丝3W,全栈开发工程师,从事多年软件开发,在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建、毕业项目实战、项目定制✌ 博主作品:《微服务实战》专栏是本人的实战经验总结,《S…...
2021年新公开工业控制系统严重漏洞汇总
声明 本文是学习ITOT一体化工业信息安全态势报告(2019). 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 工业互联网安全威胁 2021年新公开工业控制系统严重漏洞 缓冲区溢出漏洞 缓冲区溢出(buffer overflow&…...
Canvas鼠标滚轮缩放以及画布拖动(图文并茂版)
Canvas鼠标滚轮缩放以及画布拖动 本文会带大家认识Canvas中常用的坐标变换方法 translate 和 scale,并结合这两个方法,实现鼠标滚轮缩放以及画布拖动功能。 Canvas的坐标变换 Canvas 绘图的缩放以及画布拖动主要通过 CanvasRenderingContext2D 提供的 …...
[ECCV 2020] FGVC via progressive multi-granularity training of jigsaw patches
Contents IntroductionProgressive Multi-Granularity (PMG) training frameworkExperimentsReferencesIntroduction 不同于显式地寻找特征显著区域并抽取其特征,作者充分利用了 CNN 不同 stage 输出的特征图的语义粒度信息,并使用 Jigsaw Puzzle Generator 进行数据增强来帮…...
Python推导式
列表(list)推导式 [remove for source in xx_list]或者[remove for source in xx_list if condition] 实例: names[Bob,Mark,Mausk,Johndan,Wendy] new_names[name.upper() for name in names if len(name)<5] print(new_names)即迭代列…...
Java列表List的定查改增删操作
Java列表List的定查改增删操作定义查找遍历元素与下标互查修改增加删除java.util中提供了三种常用的集合类,列表List、集合Map和字典Set。这些集合类相较于数组有更多功能,并且都可以通过Iterator(迭代器)来访问。 在这篇博客中&…...
day03java语言特性 JDK、JRE、JVM
1、Java语言的特性 1.1、简单性在Java语言当中真正操作内存的是:JVM(Java虚拟机)所有的java程序都是运行在Java虚拟机当中的。而Java虚拟机执行过程中再去操作内存。对于C或者C来说程序员都是可以直接通过指针操作内存的。C或者C更灵活&…...
HydroD 实用教程(二)有限元模型
目 录一、前言二、模型种类三、单元类型四、FEM文件五、参考文献一、前言 SESAM (Super Element Structure Analysis Module)是由挪威船级社(DNV-GL)开发的一款有限元分析(FEA)系统,它以 GeniE、…...
Java中的Set集合
Set不能存储重复元素,元素无序(指的是不按照添加的顺序,List集合是按照添加顺序存储的)hashSet注:源码底层是hashMap实现的,因为hashMap是双列的,其中键是不能重复的,而hashSet是单列…...
【RabbitMQ五】——RabbitMQ路由模式(Routing)
RabbitMQ路由模式前言RabbitMQ模式的基本概念为什么要使用Rabbitmq 路由模式RabbitMQ路由模式组成元素路由模式完整代码Pom文件引入RabbtiMQ依赖RabbitMQ工具类生产者消费者1消费者2运行结果截图前言 通过本篇博客能够简单使用RabbitMQ的路由模式。 本篇博客主要是博主通过官网…...
【C语言】宏定义 结构体 枚举变量的用法
目录 一、数据类型 二、C语言宏定义 三、C语言typedef重命名 四、 #define与typedef的区别 五、结构体 六、枚举变量 补充学习一点STM32的必备基础知识 一、数据类型 二、C语言宏定义 关键字:#define 用途:用一个字符串代替一个数字,…...
锁升级之Synchronized
Synchronized JVM系统锁一个对象里如果有多个synchronized方法,同一时刻,只要有一个线程去调用其中的一个synchronized方法,其他线程只能等待!锁的是当前对象,对象被锁定后,其他线程都不能访问当前对象的其…...
基于nodejs+vue疫情网课管理系统
疫情网课也都将通过计算机进行整体智能化操作,对于疫情网课管理系统所牵扯的管理及数据保存都是非常多的,例如管理员:首页、个人中心、学生管理、教师管理、班级管理、课程分类管理、课程表管理、课程信息管理、作业信息管理、请假信息管理、上课签到管理、论坛交流…...
Zabbix 构建监控告警平台(三)
Zabbix User parametersZabbix Trigger1.Zabbix User parameters 1.1即自定义KEY 注意:mysql安装在被监测主机 [rootlocalhost ~]# yum -y install mariadb-server mariadb [rootlocalhost ~]# systemctl start mariadb [rootlocalhost ~]# mysqladmin -uroot statu…...
解锁Switch模拟潜能:Ryujinx架构深度解析与实战优化
解锁Switch模拟潜能:Ryujinx架构深度解析与实战优化 【免费下载链接】Ryujinx 用 C# 编写的实验性 Nintendo Switch 模拟器 项目地址: https://gitcode.com/GitHub_Trending/ry/Ryujinx Ryujinx作为一款采用C#开发的开源Nintendo Switch模拟器,通…...
背包问题Ⅱ与二分问题
今天我对背包问题有了更深的理解,我一定要写下来,巩固自己的思路并且,遇到新的难题二分,不管了,干就完了!!!完全背包以今天写的代码展开详细描述与解释,并附上题目#define N 1001 in…...
macOS 环境下的 Fugu14 越狱实战:从环境配置到 Unc0ver 完美激活
1. 准备工作:搭建macOS越狱环境 在开始Fugu14越狱之前,我们需要确保macOS环境配置完善。我实测发现,很多新手卡在第一步环境搭建,其实只要按顺序完成这些准备,后面流程会顺利很多。 首先需要安装Python 3.8或更高版本…...
PromptTemplate和ChatPromptTemplate的区别是什么呢?
我用最简单、最直白、一看就懂的方式给你讲清楚: PromptTemplate 和 ChatPromptTemplate 的真正区别 一句话总结 PromptTemplate 生成一段普通字符串 给补全模型/简单模型用ChatPromptTemplate 生成一整段聊天对话格式 给**聊天模型(ChatGLM、Qwen、GP…...
Qwen2.5-VL-7B-Instruct实操手册:对话历史自动保存+一键清空功能详解
Qwen2.5-VL-7B-Instruct实操手册:对话历史自动保存一键清空功能详解 1. 开篇:你的全能视觉助手来了 今天给大家介绍一个特别实用的工具——基于Qwen2.5-VL-7B-Instruct多模态大模型的视觉交互工具。这个工具专门为RTX 4090显卡优化过,用上了…...
AtlasOS系统性能优化指南:从诊断到维护的全流程解决方案
AtlasOS系统性能优化指南:从诊断到维护的全流程解决方案 【免费下载链接】Atlas 🚀 An open and lightweight modification to Windows, designed to optimize performance, privacy and security. 项目地址: https://gitcode.com/GitHub_Trending/atl…...
别再纠结了!用SpringBoot实战告诉你,图片上传选FastDFS还是MinIO(附完整代码)
SpringBoot实战:FastDFS与MinIO文件存储方案深度对比与选型指南 在当今数据驱动的互联网应用中,文件存储系统如同数字世界的基础设施,支撑着从用户头像到高清视频的各种数据存取需求。作为Java开发者,当我们面对"选择困难症&…...
为什么你的unipush消息收不到?详解个推通道状态检测与事件触发逻辑
为什么你的UniPush消息收不到?深度解析推送失效的7大关键因素 在移动应用开发中,消息推送是维系用户活跃度的核心功能之一。许多开发者在使用UniPush服务时,经常会遇到消息未能如期送达的困扰。本文将系统性地剖析消息推送失效的底层逻辑&…...
NaViL-9B多模态提示词工程:提升图文理解准确率的10个实用技巧
NaViL-9B多模态提示词工程:提升图文理解准确率的10个实用技巧 1. 认识NaViL-9B多模态模型 NaViL-9B是一款原生支持多模态交互的大语言模型,能够同时处理文本和图像输入。与传统的纯文本模型不同,它可以直接"看懂"图片内容&#x…...
自动化周报生成:OpenClaw+GLM-4.7-Flash整合多平台数据
自动化周报生成:OpenClawGLM-4.7-Flash整合多平台数据 1. 为什么需要自动化周报 每周五下午,我的心情总是特别复杂。一方面期待着周末的到来,另一方面又要面对那个令人头疼的任务——写周报。相信很多技术从业者都有类似的经历:…...
