力扣刷题-二叉树-二叉树最小深度
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。(注意题意)
示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:2
层序遍历法
# 层序遍历法
class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0queue = deque([(root, 1)]) # 每个元素是元组 一个是树元素值 一个是最小深度 比较巧妙while queue:cur, min_depth = queue.popleft()if not cur.left and not cur.right:return min_depthif cur.left:queue.append((cur.left, min_depth+1))if cur.right:queue.append((cur.right, min_depth+1))return 0
时间复杂度:O(N) 因为每个结点会访问一次
空间复杂度:O(N)在层序遍历法中空间复杂度主要取决于队列的开销,队列中的元素个数不会超过树的节点数。
递归法
注意这块和最大深度不一样,如下是错误代码:说明:叶子节点是指没有子节点的节点。(注意题意)

这个代码就犯了此图中的误区:说明:叶子节点是指没有子节点的节点。(注意题意)

如果这么求的话,没有左孩子的分支会算为最短深度。
所以,如果左子树为空,右子树不为空,说明最小深度是 1 + 右子树的深度。
反之,右子树为空,左子树不为空,最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空,返回左右子树深度最小值 + 1 。

# 递归法
class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""return self.getDepth(root)def getDepth(self, node):if node is None:return 0leftDepth = self.getDepth(node.left) # 左rightDepth = self.getDepth(node.right) # 右# 中# 当一个左子树为空,右不为空,这时并不是最低点if node.left is None and node.right is not None:return 1 + rightDepth# 当一个右子树为空,左不为空,这时并不是最低点if node.left is not None and node.right is None:return 1 + leftDepthresult = 1 + min(leftDepth, rightDepth)return result
时间复杂度:O(N),其中 N 是树的节点数。对每个节点访问一次。
空间复杂度:O(N)/O(H) 其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关,空间复杂度为 O(logN)
参考:
https://www.programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html
相关文章:
力扣刷题-二叉树-二叉树最小深度
给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。(注意题意) 示例 1: 输入:root [3,9,20,null,null,15,7] 输出&#x…...
注解方式优雅的实现 Redisson 分布式锁
1前言 日常开发中,难免遇到一些并发的场景,为了保证接口执行的一致性,通常采用加锁的方式,因为服务是分布式部署模式,本地锁Reentrantlock和Synchnorized这些就先放到一边了,Redis的setnx锁存在无法抱保证…...
PHP/Laravel通过经纬度计算距离获取附近商家
实际开发中,常常需要获取用户附近的商家,思路是 获取用户位置(经纬度信息)在数据库中查询在距离范围内的商家 注: 本文章内计算距离所使用地球半径统一为 6378.138 km public function mpa_list($latitude,$longitude,$distance){// $latitude 34.306465;// $longitude 10…...
grafana面板介绍
grafana 快速使用 背景 随着公司业务的不断发展,紧接来的是业务种类的增加、服务器数量的增长、网络环境的越发复杂以及发布更加频繁,从而不可避免地带来了线上事故的增多,因此需要对服务器到应用的全方位监控,提前预警…...
实验三 循环结构程序设计(Python)
第1关:打印图形 zm=input("") #代码开始#代码结束def print_pattern(letter):if not letter.isalpha() or not letter.isupper():print("请输入大写字母")returnstart_char = Aend_char = letterfor i in range(ord(start_char), ord(end_char) + 1):spa…...
Flutter笔记:目录与文件存储以及在Flutter中的使用(上)
Flutter笔记 目录与文件存储以及在Flutter中的使用(上) 文件系统基础知识与路径操作 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:h…...
注意了!申请流量卡时地址一定不要填写学校,不好下卡哦!
当我们在网上购买流量卡时,都会要求让填写准确的收货地址,但是对于收货地址你填对了吗? 很多朋友在提交流量卡申请之后,往往会被运营商拒审,对于拒审的原因除了比较常见的信息填写有有误、涉及禁发地区、重复申…...
minio使用shell上传文件
minio使用shell上传文件 前言1. 编写调用脚本2.测试脚本上传3.候选脚本 前言 业务场景需要实现,服务器文件上传至存储服务。一种方式是安装minio的linux客户端,另一种方式是通过调用minio的api接口实现文件上传。后一种方式不需要依赖minio的客户端使用…...
LeetCode538. Convert BST to Greater Tree
文章目录 一、题目二、题解 一、题目 Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST. As a remin…...
iPaaS和RPA,企业自动化应该如何选择?
全球著名的咨询调查机构Gartner在2022年初再次发布了《2022年12大技术趋势》报告。 Gartner是全球最具权威的IT研究与顾问咨询公司,成立于1979年,在界定及分析那些决定了商业进程的发展趋势与技术方面,它拥有二十年以上的丰富经验,…...
AI实践与学习1_Milvus向量数据库实践与原理分析
前言 随着NLP预训练模型(大模型)以及多模态研究领域的发展,向量数据库被使用的越来越多。 在XOP亿级题库业务背景下,对于试题召回搜索单单靠着ES集群已经出现性能瓶颈,因此需要预研其他技术方案提高试题搜索召回率。…...
3Dexcite deltgen 2022x 新功能
3DEXCITE DELTAGEN 2022x 现已发布,此次新版发布包含 DELTAGEN 2022x,DELTAGEN MARKETING SUITE 2022x,DELTAGEN XPLORE 2022x,以及软件开发工具包 SDK FOR DELTAGEN 2022x 版本。赶快来获取最新 DG 版本,了解新增内容…...
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形 文章链接:柱状图中最大的矩形 视频链接:柱状图中最大的矩形 1. LeetCode 84. 柱状图中最大的矩形 1.1 思路 本题是给一个数组形象得画出图后求矩形的最大面积是多少。本题和42. 接雨水…...
【2023云栖】陈守元:阿里云开源大数据产品年度发布
本文根据 2023 云栖大会演讲实录整理而成,演讲信息如下: 演讲人:陈守元 | 阿里云计算平台事业部开源大数据产品总监 演讲主题:阿里云开源大数据产品年度发布 随着云计算的不断发展,未来数据处理和应用的趋势将围绕C…...
Element UI 禁用数字输入框组件添加鼠标滚动事件
Element UI 禁用数字输入框组件添加鼠标滚动事件 <el-input type"number" mousewheel.native.prevent DOMMouseScroll.native.prevent :min"0" onkeyup"this.valuethis.value.match(/\d\.?\d{0,2}/);"v-model"form.threeYearDevelop…...
担忧CentOS停服?KeyarchOS系统来支撑
担忧CentOS停服?KeyarchOS系统来支撑 近年发生的“微软黑屏门”、“微软操作系统停更”等安全事件,敲响了我国 IT 产业的警钟,建立由我国主导的 IT 产业生态尤为迫切。对此,我国信息技术应用创新行业乘势而起,旨在通过…...
聚观早报 |联想集团Q2财季业绩;小鹏汽车Q3营收
【聚观365】11月17日消息 联想集团Q2财季业绩 小鹏汽车Q3营收 微软发布两款自研AI芯片 FAA批准SpaceX再次发射星际飞船 2023 OPPO开发者大会 联想集团Q2财季业绩 全球数字经济领导企业联想集团公布截至2023年9月30日的2023/24财年第二财季业绩:整体营收达到10…...
SAP ABAP权限控制中常用TCODE
权限控制中的几个TCODE 1.创建新的权限对象并在程序中使用 利用SU21创建权限对象Z_TEST,在程序中检查授权。 检查的代码如下: AUTHORITY-CHECK OBJECT ‘Z_TEST’ID ‘ACTION’ FIELD ‘44′ID ‘BUKRS’ FIELD DUMMY .IF sy-subrc NE 0.MESSAGE e00…...
云计算赛项容器云2023搭建
部署容器云平台[5 分] 使 用 OpenStack 私 有 云 平 台 创 建 两 台 云 主 机 , 云 主 机 类 型 使 用 4vCPU/12G/100G 类型,分别作为 Kubernetes 集群的 Master 节点和 node 节点, 然后完成 Kubernetes 集群的部署,并完成 Istio …...
11.1 文件拷贝移动与删除
在编程中,针对磁盘与目录的操作也是非常重要的,本章将重点介绍如何实现针对文件目录与磁盘的操作方法,其中包括了删除文件,文件拷贝,文件读写,目录遍历输出,遍历磁盘容量信息,磁盘格…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
