二叉树的最小深度——递归法、迭代法
1题目
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
2链接
题目:111. 二叉树的最小深度 - 力扣(Leetcode)
视频:看起来好像做过,一写就错! | LeetCode:111.二叉树的最小深度_哔哩哔哩_bilibili
3解题思路
本题前序遍历和后序遍历都可以,前序求的是深度,后序求的是高度。
二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)
二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数后者节点数(取决于高度从0开始还是从1开始)
那么使用后序遍历,其实求的是根节点到叶子节点的最小距离,就是求高度的过程,不过这个最小距离 也同样是最小深度。
以下讲解中遍历顺序上依然采用后序遍历(因为要比较递归返回之后的结果,本文我也给出前序遍历的写法)。
本题还有一个误区,在处理节点的过程中,最大深度很容易理解,最小深度就不那么好理解,如图:

这就重新审题了,题目中说的是:最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。
什么是叶子节点,左右孩子都为空的节点才是叶子节点!
3.1递归法
递归三部曲:
确定递归函数的参数和返回值
参数为要传入的二叉树根节点,返回的是int类型的深度。
代码如下:
int getDepth(TreeNode* node)确定终止条件
终止条件也是遇到空节点返回0,表示当前节点的高度为0。
代码如下:
if (node == NULL) return 0;确定单层递归的逻辑
这块和求最大深度可就不一样了,一些同学可能会写如下代码:
int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);
return result;这个代码就犯了此图中的误区:

如果这么求的话,没有左孩子的分支会算为最短深度。
所以,如果左子树为空,右子树不为空,说明最小深度是 1 + 右子树的深度。
反之,右子树为空,左子树不为空,最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空,返回左右子树深度最小值 + 1 。
3.2迭代法
层序遍历
需要注意的是,只有当左右孩子都为空的时候,才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点
4代码
4.1递归法——后序遍历
//递归法——后序遍历
class Solution {
public:int getDepth(TreeNode* root) {// 如果节点为空,深度为0if (root == nullptr) {return 0;}// 递归计算左子树的深度和右子树的深度int leftDepth = getDepth(root->left);//左int rightDepth = getDepth(root->right);//右 //后续为中// 如果当前节点左子树为空且右子树不为空,则最小深度为1加右子树的最小深度if (root->left == nullptr && root->right != nullptr) {return 1 + rightDepth;}// 如果当前节点右子树为空且左子树不为空,则最小深度为1加左子树的最小深度if (root->left != nullptr && root->right == nullptr) {return 1 + leftDepth;}// 否则,取其左右子树最小深度的较小值,并加上1作为当前节点的深度,即可得到整棵树的最小深度int result = min(leftDepth, rightDepth) + 1;return result;}int minDepth(TreeNode* root) {// 调用getDepth函数来获取root节点的最小深度,并返回计算结果return getDepth(root);}
};这段 C++ 代码中定义了一个名为 Solution 的类,其中实现了两个方法:
getDepth 函数,递归计算当前节点的深度。如果该节点左子树为空但右子树不为空,则最小深度为1加右子树的最小深度;如果该节点右子树为空但左子树不为空,则最小深度为1加左子树的最小深度;否则,返回左右子树最小深度的较小值,并加上1作为当前节点的深度,即可得到整棵树的最小深度。
minDepth 函数,调用 getDepth 函数并返回计算结果。
4.2递归法——AI生成
//递归法——后序遍历——from AI
// 时间复杂度:O(n),其中n是二叉树的节点个数。每个节点最多被访问一次,因此时间复杂度是O(n)。
// 空间复杂度:O(h),其中h是二叉树的高度。最坏情况下,二叉树呈现链状,空间复杂度是O(n);平均情况下,空间复杂度是O(logn)。
class Solution {
public:int minDepth(TreeNode* root) {if (!root) { // 如果根节点为空,返回0return 0;}if (!root->left && !root->right) { // 如果根节点左右子树都为空,返回1return 1;}int left_depth = INT_MAX; // 记录左子树最小深度if (root->left) {left_depth = minDepth(root->left); // 递归求左子树最小深度}int right_depth = INT_MAX; // 记录右子树最小深度if (root->right) {right_depth = minDepth(root->right); // 递归求右子树最小深度}return min(left_depth, right_depth) + 1; // 返回左右子树最小深度加1的最小值}
};该函数的输入参数为二叉树的根节点 root,返回值为二叉树的最小深度。首先判断根节点是否为空,如果为空,直接返回深度为0;如果根节点的左右子树都为空,说明当前节点为叶子节点,返回深度为1。
然后,定义变量 left_depth 和 right_depth 分别记录左右子树的最小深度。如果当前节点有左子树,递归调用 minDepth 函数计算左子树的最小深度;同样的,如果当前节点有右子树,则递归计算右子树的最小深度。然后,返回左右子树最小深度加1的最小值。
这个递归算法的思路是:每次从根节点开始,递归计算左右子树的最小深度,然后返回左右子树最小深度加1的最小值,即为整棵树的最小深度。
4.3迭代法
//迭代法——层序遍历
class Solution{
public:int minDepth(TreeNode* root) {// 如果节点为空,返回深度为0if (root == nullptr) return 0;// 创建一个队列,将根节点加入队列中,初始深度为0queue<TreeNode*> que;que.push(root);int depth = 0;// 循环遍历队列中的每个节点,直到队列为空while (!que.empty()) {// 记录当前队列的大小,该大小等于当前层节点的数目int size = que.size();// 每次遍历队列中的所有节点时,深度加1depth++;// 遍历当前层的所有节点,将下一层的节点加入队列中for (int i = 0; i < size; i++) {// 取出队首节点TreeNode* node = que.front();que.pop();// 将左右子节点加入队列中if (node->left) que.push(node->left);if (node->right) que.push(node->right);// 如果该节点同时没有左右子节点,返回当前深度if (!node->left && !node->right) return depth;}}// 如果整棵树根节点为0,返回深度为0return depth;}
};这段代码定义了一个名为 Solution 的类,其中实现了一个 minDepth 函数,该函数用于计算一棵二叉树的最小深度。
该函数的输入参数为二叉树的根节点 root,返回值为二叉树的最小深度。如果 root 节点为空,直接返回深度为0。否则,创建一个队列 que,将 root 节点加入队列中,并初始化深度为0。
然后,执行一个循环,每次循环遍历队列中的所有节点,直到队列为空。在循环内,首先记录当前队列的大小 size,该大小等于当前层节点的数目;然后,将深度 depth 加1,表示进入了下一层;遍历当前层的所有节点,将每个节点的左右子节点加入队列中;如果该节点同时没有左右子节点,说明已经到达最小深度,返回当前深度。
如果循环结束后仍然没有找到任何叶子节点,则整棵树只有根节点,返回深度为1。
相关文章:
二叉树的最小深度——递归法、迭代法
1题目给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明:叶子节点是指没有子节点的节点。示例 1:输入:root [3,9,20,null,null,15,7]输出:2示例 2:输入&…...
Vue中常使用的三种刷新页面的方式
一、通过js原始方法刷新 缺点: 出现闪白 目录 一、通过js原始方法刷新 二、通过Vue自带的路由进行跳转 三、通过在APP页面进行demo进行刷新(推荐) 1.vue2写法 2. vue3.2写法 <template><div><div class"header"><button clic…...
【Shell】脚本
Shell脚本脚本格式第一个Shell脚本:hello.sh脚本常用执行方式1. bash或sh脚本的相对路径或绝对路径2. 输入脚本的绝对路径或相对路径3. 在脚本的路径前加上.或者source脚本格式 脚本以#!/bin/bash开头(指定解析器) #! 是一个约定的标记&…...
Mybatis的多表操作
1.Mybatis多表查询 1.1一对一查询 1.一对一查询的模型 用户表和订单表的关系为,一个用户有多个订单,一个订单只从属于一个用户 一对一查询的需求:查询一个订单,与此同时查询出该订单所属的用户2.创建Order和User实体public class…...
【JVM】字节码指令全解
文章目录 入门案例原始 java 代码编译后的字节码文件常量池载入运行时常量池方法字节码载入方法区main 线程开始运行,分配栈帧内存执行引擎开始执行字节码bipush 10istore_1ldc #3istore_2iload_1iload_2iaddistore_3getstatic #4iload_3invokevirtual #5return条件判断指令循…...
【精品】华为认证数通HCIA+HCIP题库分享(含答案解析)
嗨~大家好久不见,我是薄荷学姐,随着华为业务也全球领域的迅猛发展,越来越多人开始重视华为认证的重要性。今天给大家分享一下去年8月份的题库,基本都是一样,希望可以帮助到大家哈想要通过华为认证,除了进行…...
Qt cmake 资源文件的加载
Qt cmake 资源文件的加载概述qt_add_resourcesqt5_add_resourcesqt6_add_resources是否需要加载qrc文件需要加载qrc的情况不需要加载qrc的情况C 代码加载示例加载PNG加载CSS文件加载qrc文件Qt6相对于Qt5的一些变化Qt6和Qt5在加载资源文件方面的区别主要集中在两个方面ÿ…...
【链表OJ题(九)】环形链表延伸问题以及相关OJ题
环形链表OJ题 1. 环形链表 链接:141. 环形链表 描述: 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环&…...
【C++初阶】四、类和对象(下)
文章目录一、再谈构造函数构造函数体赋值初始化列表explicit关键字二、Static成员引入- 计算类中创建了多少个类对象概念特性静态成员函数的访问三、友元友元函数友元类四、内部类五、匿名对象六、拷贝对象时的一些编译器优化一、再谈构造函数 构造函数体赋值 在创建对象时&a…...
IDEA maven没有Import Maven projects automatically解决办法
去年装了个 IDEA2022版本 配置maven时我才发现是个大坑 他没有import Maven projects automatically配置项 当时看到我人都麻了 然后项目呢 用了依赖 这东西还不会自动下依赖 整的我那是相当难受 还在最后还是找到了解决办法 我们在配置文件上点击右键 然后鼠标选择如下图选项…...
Java实习生------MySQL10道面试题打卡
今日语录:“没有执行力,就没有竞争力 ”🌹 参考资料:图解MySQL、MySQL面试题 1、事务有哪些特性? 原子性: 一个事务中的所有操作,要么全部完成,要么全部不完成,不会出现…...
帆软报表设计器 数据集之数据库查询
当点击数据库查询时,调用TableDataTreePane的 public void actionPerformed(ActionEvent var1) {TableDataTreePane.this.dgEdit(this.getTableDataInstance().creatTableDataPane(), TableDataTreePane.this.createDsName(this.getNamePrefix()), false);} 然后调用TableDat…...
CSDN 第三十七期竞赛题解
很少有时间来玩玩题目,上一次因为环境极为嘈杂的原因在时间上没有进入前十,挺遗憾的。 在 CSDN 参加的第一次没出锅的比赛。 大概只有最后一题值得好好讲讲。 T1:幼稚班作业 幼稚园终于又有新的作业了。 老师安排同学用发给同学的4根木棒拼接…...
Vue实战【常用的Vue小魔法】
目录🌟前言🌟能让你首次加载更快的路由懒加载,怎么能忘?🌟你是否还记得有一个叫Object.freeze的方法?🌟异步组件那么强,你是不是没用过?🌟你是不是还在comput…...
用C跑爬虫
爬虫自指定的URL地址开始下载网络资源,直到该地址和所有子地址的指定资源都下载完毕为止。 下面开始逐步分析爬虫的实现。 待下载集合与已下载集合 为了保存需要下载的URL,同时防止重复下载,我们需要分别用了两个集合来存放将要下载的URL和…...
【C语言】你真的了解结构体吗
引言✨我们知道C语言中存在着整形(int、short...),字符型(char),浮点型(float、double)等等内置类型,但是有时候,这些内置类型并不能解决我们的需求,因为我们无法用这些单一的内置类型来描述一些复杂的对象,…...
血氧仪是如何得出血氧饱和度值的?
目录 一、血氧饱和度概念 二、血氧饱和度监测意义 三、血氧饱和度的监测方式 四、容积脉搏波计算血氧饱和度原理 五、容积脉搏波波形的测量电路方案 1)光源和光电探测器的集成测量模块:SFH7050—反射式 2)模拟前端 六、市面上血氧仪类型…...
Java全栈知识(3)接口和抽象类
1、抽象类 抽象类就是由abstract修饰的类,其中没有只声明没有实现的方法就是抽象方法,抽象类中可以有0个或者多个抽象方法。 1.1、抽象类的语法 抽象类不能被final修饰 因为抽象类是一种类似于工程中未完成的中间件。需要有子类进行继承完善其功能,所…...
JavaScript == === Object.is()
文章目录JavaScript & & Object.is() 相等运算符 全等运算符Object.is() 值比较JavaScript & & Object.is() 相等运算符 相等运算符,会先进行类型转换,将2个操作数转为相同的类型,再比较2个值。 console.log("10&…...
GPT4论文翻译 by GPT4 and Human
GPT-4技术报告解读 文章目录GPT-4技术报告解读前言:摘要1 引言2 技术报告的范围和局限性3 可预测的扩展性3.1 损失预测3.2 人类评估能力的扩展4 能力评估4.1 视觉输入 !!!5 限制6 风险与缓解:7 结论前言: 这篇报告内容太多了!&am…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
Win系统权限提升篇UAC绕过DLL劫持未引号路径可控服务全检项目
应用场景: 1、常规某个机器被钓鱼后门攻击后,我们需要做更高权限操作或权限维持等。 2、内网域中某个机器被钓鱼后门攻击后,我们需要对后续内网域做安全测试。 #Win10&11-BypassUAC自动提权-MSF&UACME 为了远程执行目标的exe或者b…...
