C++力扣题目111--二叉树的最小深度
力扣题目链接(opens new window)
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],

返回它的最小深度 2
思路
看完了这篇104.二叉树的最大深度 (opens new window),再来看看如何求最小深度。
直觉上好像和求最大深度差不多,其实还是差不少的。
本题依然是前序遍历和后序遍历都可以,前序求的是深度,后序求的是高度。
- 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)
- 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数后者节点数(取决于高度从0开始还是从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 。
代码如下:
int leftDepth = getDepth(node->left); // 左
int rightDepth = getDepth(node->right); // 右// 中
// 当一个左子树为空,右不为空,这时并不是最低点
if (node->left == NULL && node->right != NULL) { return 1 + rightDepth;
}
// 当一个右子树为空,左不为空,这时并不是最低点
if (node->left != NULL && node->right == NULL) { return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;
遍历的顺序为后序(左右中),可以看出:求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
整体递归代码如下:
class Solution {
public:int getDepth(TreeNode* node) {if (node == NULL) return 0;int leftDepth = getDepth(node->left); // 左int rightDepth = getDepth(node->right); // 右// 中// 当一个左子树为空,右不为空,这时并不是最低点if (node->left == NULL && node->right != NULL) { return 1 + rightDepth;} // 当一个右子树为空,左不为空,这时并不是最低点if (node->left != NULL && node->right == NULL) { return 1 + leftDepth;}int result = 1 + min(leftDepth, rightDepth);return result;}int minDepth(TreeNode* root) {return getDepth(root);}
};
精简之后代码如下:
class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right != NULL) {return 1 + minDepth(root->right);}if (root->left != NULL && root->right == NULL) {return 1 + minDepth(root->left);}return 1 + min(minDepth(root->left), minDepth(root->right));}
};
精简之后的代码根本看不出是哪种遍历方式,所以依然还要强调一波:如果对二叉树的操作还不熟练,尽量不要直接照着精简代码来学。
前序遍历的方式:
class Solution {
private:int result;void getdepth(TreeNode* node, int depth) {// 函数递归终止条件if (node == nullptr) {return;}// 中,处理逻辑:判断是不是叶子结点if (node -> left == nullptr && node->right == nullptr) {result = min(result, depth);}if (node->left) { // 左getdepth(node->left, depth + 1);}if (node->right) { // 右getdepth(node->right, depth + 1);}return ;}public:int minDepth(TreeNode* root) {if (root == nullptr) {return 0;}result = INT_MAX;getdepth(root, 1);return result;}
};
#迭代法
相对于104.二叉树的最大深度 (opens new window),本题还可以使用层序遍历的方式来解决,思路是一样的。
如果对层序遍历还不清楚的话,可以看这篇:二叉树:层序遍历登场!(opens new window)
需要注意的是,只有当左右孩子都为空的时候,才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点
代码如下:(详细注释)
class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;int depth = 0;queue<TreeNode*> que;que.push(root);while(!que.empty()) {int size = que.size();depth++; // 记录最小深度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;}}}return depth;}
};相关文章:
C++力扣题目111--二叉树的最小深度
力扣题目链接(opens new window) 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 返回它的最小深度 2 思路 看完了这篇104.二…...
【图像拼接】源码精读:Adaptive As-Natural-As-Possible Image Stitching(AANAP/ANAP)
第一次来请先看这篇文章:【图像拼接(Image Stitching)】关于【图像拼接论文源码精读】专栏的相关说明,包含专栏内文章结构说明、源码阅读顺序、培养代码能力、如何创新等(不定期更新) 【图像拼接论文源码精读】专栏文章目录 【源码精读】As-Projective-As-Possible Imag…...
解决docker run报错:Error response from daemon: No command specified.
将docker镜像export/import之后,对新的镜像执行docker run时报错: docker: Error response from daemon: No command specified. 解决方法: 方案1: 查看容器的command: docker ps --no-trunc 在docker run命令上增加…...
算法第十二天-最大整除子集
最大整除子集 题目要求 解题思路 来自[宫水三叶] 根据题意:对于符合要求的[整除子集]中的任意两个值,必然满足[较大数]是[较小数]的倍数 数据范围是 1 0 3 10^3 103,我们不可能采取获取所有子集,再检查子集是否合法的暴力搜解法…...
简单易懂的PyTorch 损失函数:优化机器学习模型的关键
目录 torch.nn子模块Loss Functions详解 nn.L1Loss 用途 用法 使用技巧 注意事项 代码示例 nn.MSELoss 用途 用法 使用技巧 注意事项 代码示例 nn.CrossEntropyLoss 用途 用法 使用技巧 注意事项 代码示例 使用类别索引 使用类别概率 nn.CTCLoss 用途 …...
Kubernetes/k8s的存储卷/数据卷
k8s的存储卷/数据卷 容器内的目录和宿主机的目录挂载 容器在系统上的生命周期是短暂的,delete,k8s用控制创建的pod,delete相当于重启,容器的状态也会回复到初始状态 一旦回到初始状态,所有的后天编辑的文件都会消失…...
【漏洞复现】锐捷RG-UAC统一上网行为管理系统信息泄露漏洞
Nx01 产品简介 锐捷网络成立于2000年1月,原名实达网络,2003年更名,自成立以来,一直扎根行业,深入场景进行解决方案设计和创新,并利用云计算、SDN、移动互联、大数据、物联网、AI等新技术为各行业用户提供场…...
Android - 串口通讯(SerialPort)
最早的博客Android 模拟串口通信过程_launch virtual serial port driver pro-CSDN博客里就是用过 Google 提供的 demo,最近想再写个其他的demo发现用起来有点麻烦,还需要导入其他 module,因此在网上找到了Android-SerialPort-API: https://g…...
如何使用設置靜態住宅IP
靜態住宅IP就是一種靜態的、分配給住宅用戶的IP地址。與動態IP地址不同,靜態住宅IP一旦分配給用戶,就會一直保持不變,除非ISP(Internet Service Provider,互聯網服務提供商)進行手動更改。那麼,…...
在学习爬虫前的准备
1. 写一个爬虫程序需要分几步 获取网页内容。 我们会通过代码给一个网站服务器发送请求,它会返回给我们网页上的内容。 在我们平时使用浏览器访问服务器内容是,本质上也是向服务器发送一个请求,然后服务器返回网页上的内容。只不过浏览器还会…...
windows下安装oracle-win-64-11g超详细图文步骤
官方下载地址:点这里 1.根据自己电脑情况,解压64或者32位客户端,以及database压缩包 2.解压后双击执行database文件夹下的setup.exe 3.详细的安装步骤 (1)数据库安装 一、配置安全更新 电子邮件可写可不写…...
Go模板后端渲染时vue单页面冲突处理
go后端模版语法是通过 {{}} ,vue也是通过双花括号来渲染的,如果使用go渲染vue的html页面的时候就会报错,因为分别不出来哪个是vue的,哪个是go的,既可以修改go的模板语法 template.New("output").Delims(&qu…...
笔记本摄像头模拟监控推送RTSP流
使用笔记本摄像头模拟监控推送RTSP流 一、基础安装软件准备 本文使用软件下载链接:下载地址 FFmpeg软件: Download ffmpeg 选择Windows builds by BtbN 一个完整的跨平台解决方案,用于录制、转换和流式传输音频和视频。 EasyDarwin软件:Download Easy…...
鸿蒙开发已解决-ArkTS编译时遇到arkts-no-obj-literals-as-types错误
文章目录 项目场景:问题描述原因分析:解决方案:解决方案1解决方案2此Bug解决方案总结项目场景: 在开发鸿蒙项目过程中,遇到了arkts-no-obj-literals-as-types,总结了自己和网上人的解决方案,故写下这篇文章。 遇到问题: rkTS编译时遇到arkts-no-obj-literals-as-type…...
实现目标检测中的数据格式自由(labelme json、voc、coco、yolo格式的相互转换)
在进行目标检测任务中,存在labelme json、voc、coco、yolo等格式。labelme json是由anylabeling、labelme等软件生成的标注格式、voc是通用目标检测框(mmdetection、paddledetection)所支持的格式,coco是通用目标检测框࿰…...
一文读懂JVS逻辑引擎如何调用规则引擎:含详细步骤与场景示例
在当今的数字化时代,业务逻辑和规则的复杂性不断增加,这使得逻辑引擎和规则引擎在处理业务需求时显得尤为重要。逻辑引擎和规则引擎通过定义、解析和管理业务逻辑和规则,能够帮助企业提高工作效率、降低运营成本,并增强决策的科学…...
苹果应用上架是否需要软件著作权?
苹果应用上架是否需要软件著作权? 摘要 随着移动互联网的发展,苹果应用在市场上占据了很大份额。但是,很多开发者在上传苹果应用到App Store时,都会遇到一个问题,即是否需要进行软著申请?本文将深入探讨这…...
LDD学习笔记 -- Linux字符设备驱动
LDD学习笔记 -- Linux字符设备驱动 虚拟文件系统 VFS设备号相关Kernel APIs动态申请设备号动态创建设备文件内核空间和用户空间的数据交换系统调用方法readwritelseek 写一个伪字符设备驱动在主机上测试pcd(HOST)在目标板上测试pcd(TARGET) 字符驱动程序用于与Linux内核中的设备…...
杰理AC63串口收发实例
在event.h文件中预定义串口消息 #define DEVICE_EVENT_FROM_MY_UART ((M << 24) | (Y << 16) | (U << 8) | \0)在app_spp_and_le.c文件里对SYS_DEVICE_EVENT做处理,添加收到DEVICE_EVENT_FROM_MY_UART消息时的处理函数my_rx_handler(); cas…...
麦芯(MachCore)开发教程1 --- 设备软件中间件
黄国强 2024/1/10 acloud163.com 对任何公司来说,在短时间内开发一款高质量设备专用软件,是一件不太容易做到的事情。麦芯是笔者发明的一款设备软件中间件产品。麦芯致力于给设备厂商提供一个开发工具和平台,让客户快速高效的开发自己的设备专…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
