( “树” 之 DFS) 111. 二叉树的最小深度 ——【Leetcode每日一题】

111. 二叉树的最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例 1:

在这里插入图片描述

输入:root = [3,9,20,null,null,15,7]
输出:2

示例 2:

在这里插入图片描述

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5

提示:

  • 树中节点数的范围在 [0, 105] 内
  • -1000 <= Node.val <= 1000

思路:DFS

首先可以想到使用深度优先搜索的方法,遍历整棵树,记录最小深度。

  • 对于每一个非叶子节点,我们只需要分别计算其左右子树的最小叶子节点深度。
    • 如果左右子树其中一个为null,则返回另一个不为空子树的最小深度;
    • 如果都不为空,则返回左右子树最小深度的最小值。
  • 对于叶子节点则返回。

这样就将一个大问题转化为了小问题,可以递归地解决该问题。

代码:(Java、C++)

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        return dfs(root);
    }
    public int dfs(TreeNode root){
        if(root.left == null && root.right == null) return 1;
        if(root.left == null) return 1 + minDepth(root.right);
        if(root.right == null) return 1 + minDepth(root.left);
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL) return 0;
        return dfs(root);
    }
    int dfs(TreeNode* root){
        if(root->left == NULL && root->right == NULL) return 1;
        if(root->left == NULL) return 1 + minDepth(root->right);
        if(root->right == NULL) return 1 + minDepth(root->left);
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

运行结果:

在这里插入图片描述

复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 是树的节点数。对每个节点访问一次。
  • 空间复杂度 O ( h e i g h t ) O(height) O(height),其中 height 是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为 O ( n ) O(n) O(n)。平均情况下树的高度与节点数的对数正相关,空间复杂度为 O ( l o g ⁡ n ) O(log⁡n) O(logn)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/12920.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Nginx 正向代理、方向代理、端口转发

正向代理就是客户端代理&#xff0c;代理客户端&#xff0c;服务端不知道实际发起请求的客户端 正向代理中&#xff0c;proxy和client一般同一个lan或者网络可达&#xff0c;server与client一般不可达&#xff08;缓存场景除外&#xff09; 正向代理类似一个跳板机&#xff0c…

java异常

下面是算术异常。 抛出的异常其实是个类。 下面是空指针异常。 用异常时&#xff0c;下面语句不会执行。 上面这些是运行时异常 下面这是编译时异常。 在程序编译期间发生的异常&#xff0c;称为编译时异常&#xff0c;也称为受检查异常 在程序执行期间发生的异常&#xff0c;…

企业信息化建设该怎么做?方向和手段都在这了

企业信息化建设该怎么做&#xff1f; 如果现在是十年前&#xff0c;我一定会说&#xff0c;做信息化需要寻找熟悉不同编程语言、有经验的程序员。 但是现在&#xff0c;如果不是特别复杂的信息化系统&#xff0c;其实公司完全可以使用零代码平台自主开发&#xff0c;不需要再…

TryHackMe-Year of the Jellyfish(linux渗透测试)

Year of the Jellyfish 请注意 - 此框使用公共 IP 进行部署。想想这对你应该如何应对这一挑战意味着什么。如果您高速枚举公共 IP 地址&#xff0c;ISP 通常会不满意… 端口扫描 循例nmap 扫描结果中还有域名&#xff0c;加进hosts FTP 枚举 尝试anonymous Web枚举 有三个端…

Open Inventor 2023.1 Crack

发行说明 Open Inventor 2023.1&#xff08;次要版本&#xff09; 文档于 2023 年 4 月发布。 此版本中包含的增强功能和新功能&#xff1a; Open Inventor 10 版本编号更改体积可视化 单一分辨率的体绘制着色器中与裁剪和 ROI 相关的新功能MeshVizXLM 在 C 中扩展的剪辑线提…

[网络安全]第三次作业

目录 1. 什么是IDS&#xff1f; 2. IDS和防火墙有什么不同&#xff1f; 3. IDS工作原理&#xff1f; 4. IDS的主要检测方法有哪些详细说明&#xff1f; 5. IDS的部署方式有哪些&#xff1f; 6. IDS的签名是什么意思&#xff1f;签名过滤器有什么作用&#xff1f;例外签名…

SpringBootApplication最详细注解

SpringBootApplication最详细注解 SpringBootApplication的注解分类1.Target 2.Retention3.Document 4.Inherited5.SpringBootConfiguration 6.EnableAutoConfiguration6.1AutoConfigurationPackage这个注解6.1.1 Import6.1.2 AutoConfigurationpackages.Registrar.class 6.2 A…

经营软件公司五年,从外包到SaaS的踩坑笔记

文章目录 摘要开公司的两个误区关于管理关于合作关于SaaS其他经验大和强是两码事。大不是目的&#xff0c;强才是。小步试错、慢慢迭代不要掉入流量陷阱 摘要 经营公司已有五年&#xff0c;经历了三年的疫情停滞&#xff0c;现在正在转型为一家SaaS公司。虽然曾经迷茫过&#…

【虹科案例】固态量子发射器——虹科数字化仪用于控制钻石色心中的脉冲序列

前言 钻石的色心是晶格中的缺陷&#xff0c;其中碳原子被不同种类的原子取代&#xff0c;相邻的晶格位置是空的。由于其明亮的单光子发射和光学可访问的自旋&#xff0c;色心可以成为未来量子信息处理和量子网络的有前途的固态量子发射器。 实现自旋量子比特和相干光子纠缠的两…

Linux DHCP服务

DHCP 作用 DHCP动态主机配置协议作为服务端负责集中给客户端分配各种网络地址参数(主要包括IP地址、子网掩码、广播地址、默认网关地址、DNS服务器地址) 传输协议端口 服务端 UDP 67端口 客户端 UDP 68端口 工作原理 1) 客户端广播发送DISCOVER报文寻找服务端 2) 服务端广播发…

5G物理层信道pdcch说明(留档)

网络七层协议OSI是一个开放性的通信系统互连参考模型。 它是国际标准组织制定的一个指导信息互联、互通和写作的网络规范。 开放&#xff1a;是指只要遵循OSI标准&#xff0c;位于世界的任何地方的任何系统之间都可以进行通讯&#xff1b;开放系统&#xff1a;是指遵循互联网协…

MBD—模型的回调函数

目录 前面 如何设置&#xff1f; 应用 简单的提示 数据的初始化 前面 常用的回调函数有三类&#xff1a;模型的回调函数、模块的回调函数、信号的回调函数。这里分享一下模型的回调函数。 回调函数就是CallBack. 如何设置&#xff1f; 打开一个模型&#xff0c;在空白…

论文阅读【17】Dynamic ensemble learning for multi-label classification

论文十问十答&#xff1a; Q1论文试图解决什么问题&#xff1f; Q2这是否是一个新的问题&#xff1f; Q3这篇文章要验证一个什么科学假设&#xff1f; Q4有哪些相关研究&#xff1f;如何归类&#xff1f;谁是这一课题在领域内值得关注的研究员&#xff1f; Q5论文中提到的解决方…

简述API(电商数据API)网关的概念和功能

API 网关 ( API gateway ) 前言 在 IOT &#xff08; 物联网 &#xff09;中&#xff0c;当我们的一些设备。例如&#xff08; 监控、传感器等 &#xff09;需要将收集到的数据和信息进行汇总时&#xff0c;我们就需要一个 API。&#xff08;如果你需要Taobao/JD/pinduoduo平台…

Replicator简介

Replicator 文章目录 ReplicatorReplicator简介合成数据训练背后的理论Replicator核心组件已知的问题 Replicator简介 Omniverse Replicator 是一个高度可扩展的框架&#xff0c;构建在可扩展的 Omniverse 平台上&#xff0c;可生成物理上准确的 3D 合成数据&#xff0c;以加速…

OpenAI-ChatGPT最新官方接口《语音智能转文本》全网最详细中英文实用指南和教程,助你零基础快速轻松掌握全新技术(六)(附源码)

Speech to text 语音智能转文本 Introduction 导言Quickstart 快速开始Transcriptions 转录python代码cURL代码 Translations 翻译python代码cURL代码 Supported languages 支持的语言Longer inputs 长文件输入Prompting 提示其它资料下载 Speech to text 语音转文本 Learn how…

Mac配置QT

Mac配置QT 前言&#xff1a; 系统版本&#xff1a;Ventura 13.2.1 (22D68) 先安装homebrew&#xff0c;参考&#xff1a; https://blog.csdn.net/ZCC361571217/article/details/127333754 Mac配置&#xff1a; 安装Qt与Qt Creator&#xff1a; 通过Homebrew安装(若没Homeb…

用Spring Doc代替Swagger

1 OpenApi OpenApi 是一个业界的 API 文档标准&#xff0c;是一个规范&#xff0c;这个规范目前有两大实现&#xff0c;分别是&#xff1a; SpringFoxSpringDoc 其中 SpringFox 其实也就是我们之前所说的 Swagger&#xff0c;SpringDoc 则是我们今天要说的内容。 OpenApi 就…

【Python_Scrapy学习笔记(十三)】基于Scrapy框架的图片管道实现图片抓取

基于Scrapy框架的图片管道实现图片抓取 前言 本文中介绍 如何基于 Scrapy 框架的图片管道实现图片抓取&#xff0c;并以抓取 360 图片为例进行展示。 正文 1、Scrapy框架抓取图片原理 利用 Scrapy 框架提供的图片管道类 ImagesPipeline 抓取页面图片&#xff0c;在使用时需…

快速部署个人-ChatGPT Next Web

前提&#xff1a;要有梯子、谷歌账号。 目录 一、源码地址&#xff1a; 二、演示地址&#xff1a; 三、获取API密钥 四、 部署 五、重新部署 一、源码地址&#xff1a; GitHub - Yidadaa/ChatGPT-Next-Web: One-Click to deploy well-designed ChatGPT web UI on Verc…
最新文章