力扣每日一题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

面试中遇到过这道题?

1/5

通过次数

685.3K

提交次数

1.3M

通过率

54.0%

方法一:广度优先搜索

根节点的深度为1,从根节点开始搜索,每次搜索一层深度+1,若是搜索某一层时,发现了叶子节点,说明该叶子是层数最低的叶子,就返回该叶子的深度。

class Solution {
public:int minDepth(TreeNode* root) {if(!root) return 0;queue<TreeNode*> pq;int depth=0;pq.push(root);while(!pq.empty()){depth++;int n=pq.size();for(int i=0;i<n;i++){TreeNode *p=pq.front();pq.pop();if(!p->left&&!p->right) return depth;if(p->left) pq.push(p->left);if(p->right) pq.push(p->right);}}return depth;}
};

方法二:广度优先搜索

树的最小深度=min(左子树的最小深度,右子树的最小深度)+1。

叶子结点的深度为1,空节点的深度为0。

这种方法我没写,下面是官解。

class Solution {
public:int minDepth(TreeNode *root) {if (root == nullptr) {return 0;}if (root->left == nullptr && root->right == nullptr) {return 1;}int min_depth = INT_MAX;if (root->left != nullptr) {min_depth = min(minDepth(root->left), min_depth);}if (root->right != nullptr) {min_depth = min(minDepth(root->right), min_depth);}return min_depth + 1;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Linux网络部分——DHCP、FTP

目录 一、DHCP动态主机配置协议 1. DHCP工作原理&#xff08;流程&#xff09; 2. 使用DHCP的好处 3.DHCP的分配方式 4.DHCP安装和配置【☆】 二、FTP文件传输协议 1. FTP传输模式 2.FTP安装与配置【☆】 3. FTP设置白名单和黑名单【☆】 一、DHCP动态主机配置协议 DH…

RK3568 学习笔记 : 精简 u-boot env 默认复杂的多种引导启动设置

前言 环境&#xff1a; 正点原子 Atompi-CA1 RK3568 开发板、正点原子 DLRK3568 开发板&#xff0c;&#xff08;一时脑热买了两块 RK3568 开发板&#xff09;&#xff0c;Atompi-CA1 RK3568 开发板比较小巧&#xff0c;利于一些前期的嵌入式 Linux 开发学习与实践。 RK3568 开…

大气网格化精细化监管监测哪家好?

一、什么是大气网格化精细化监管监测 在当今环境问题日益突出的时代&#xff0c;大气质量监测与监管成为了至关重要的工作。大气网格化精细化监管监测系统的出现&#xff0c;为我们更好地了解和掌握大气环境状况提供了有力手段。然而&#xff0c;面对众多的系统供应商&#xff…

【面试经典 150 | 数组】文本左右对齐

文章目录 写在前面Tag题目来源解题思路方法一&#xff1a;模拟 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题涉及到的数据结构等内容进行回顾…

有没有适合制造企业用的研发项目管理软件?制造业选型案例必看!“追觅”上线奥博思项目管理软件,加速项目交付

智能清洁家电赛道的领军者&#xff1a;追觅科技&#xff08;苏州&#xff09;有限公司&#xff08;以下简称“追觅”&#xff09;成功上线奥博思 PowerProject 数字化项目管理系统。通过 PowerProject 系统&#xff0c;追觅公司能够实现项目全流程的覆盖&#xff0c;从预研阶段…

Coze扣子开发指南:怎么使用功能强大的插件?

●插件是什么&#xff1f; 想象一下&#xff0c;你的机器人是一个玩具车&#xff0c;它本来只能跑直线。但是&#xff0c;如果你给它装上一些额外的小配件&#xff0c;比如翅膀&#xff0c;它就能飞&#xff1b;装上轮子&#xff0c;它就能在各种地形上跑。这些小配件&#xf…

2010NOIP普及组真题 2. 接水问题

线上OJ&#xff1a; 一本通&#xff1a;http://ybt.ssoier.cn:8088/problem_show.php?pid1950 解法一、朴素模拟 核心思想&#xff1a; 朴素模拟&#xff1a; 1、先给每个b[i]水龙头分配一个人a[i]&#xff0c;b[i] 表示水龙头的剩余时间。同时标记该水龙头为 used 使用中 2…

黑马程序员——mysql——day07——MyBatis配置文件和映射文件

目录&#xff1a; 框架概述 目标什么是框架框架解决的问题 解决了技术通用的问题提升了开发效率提升了系统稳定性小结mybatis框架介绍 目标mybatis框架介绍 mybatis的优点mybatis的不足官方网站及框架包下载mybatis框架整体架构MyBatis的ORM方式小结MyBatis框架入门开发【掌握…

柒拾叁- 数据分析师都在干嘛?

1. 数据分析师 其实很多人对这个词会有不同的 定义&#xff0c;更有甚者很多业务部门也会专门 成立 一个组来进行自己业务的 数据分析。 这岗位最根本的 工作 ( 或者叫 行为 吧 )&#xff0c;就是处理 因业务而产生的数据 &#xff0c;然后给反馈 ( 提供业务相关 洞察与建议 或…

从0开始学python(二)

目录 前言 1、变量与常量 1.1命名规则 2、变量类型 2.1数值类型 2.1.1整数类型 2.1.2浮点数类型 2.2字符串类型 2.2.1转义字符 2.2.2字符串的索引和切片 2.3布尔类型 总结 前言 在上一篇文章中我们讲到了python的两个函数&#xff1a;print和input。以及保留…

【数据库】MySQL安装与卸载

文章目录 [toc]MySQL下载网盘链接下载网址 MySQL安装解压生成data文件安装MySQL启动MySQL服务 MySQL登录设置root用户密码 环境变量配置MySQL卸载 个人主页&#xff1a;丷从心 系列专栏&#xff1a;MySQL 学习指南&#xff1a;数据库 MySQL下载 网盘链接 链接&#xff1a;h…

基于Java EE平台项目管理系统的设计与实现(论文 + 源码)

【免费】基于javaEE平台的项目管理系统.zip资源-CSDN文库https://download.csdn.net/download/JW_559/89267688 基于Java EE平台项目管理系统的设计与实现 摘 要 随着社会信息化的发展&#xff0c;很多的社会管理问题也一并出现了根本性变化&#xff0c;项目公司的报表及文…

多线程系列(三) -synchronized 关键字使用详解

一、简介 在之前的线程系列文章中&#xff0c;我们介绍了线程创建的几种方式以及常用的方法介绍。 今天我们接着聊聊多线程线程安全的问题&#xff0c;以及解决办法。 实际上&#xff0c;在多线程环境中&#xff0c;难免会出现多个线程对一个对象的实例变量进行同时访问和操…

牛客NC383 主持人调度(一)【简单 排序 Java/Go/C++】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/e160b104354649b69600803184094adb 思路 直接看代码&#xff0c;不难Java代码 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修改&#xff0c;直接返…

学习如何使用PyQt5实现notebook功能

百度搜索“pyqt5中notebook控件”&#xff0c;AI自动生成相应例子的代码。在 PyQt5 中&#xff0c;QTabWidget 类被用作 Notebook 控件。以下是一个简单的示例&#xff0c;展示如何创建一个带有两个标签的 Notebook 控件&#xff0c;并在每个标签中放置一些文本。 import sys f…

伺服电机初识

目录 一、伺服电机的介绍二、伺服电机的基本原理三、伺服电机的技术特点四、伺服电机的分类五、实际产品介绍1、基本技术规格&#xff1a;2、MD42电机硬件接口3、通讯协议介绍3.1 通讯控制速度运行3.2 通讯控制位置运行3.3 通讯控制转矩运行 4、状态灯与报警信息 一、伺服电机的…

45. UE5 RPG 增加角色受击反馈

在前面的文章中&#xff0c;我们实现了对敌人的属性的初始化&#xff0c;现在敌人也拥有的自己的属性值&#xff0c;技能击中敌人后&#xff0c;也能够实现血量的减少。 现在还需要的就是在技能击中敌人后&#xff0c;需要敌人进行一些击中反馈&#xff0c;比如敌人被技能击中后…

40.乐理基础-拍号-什么是一拍

拍&#xff1a; 首先 以Y分音符的时长为一拍 这一句话&#xff0c;然后拍是音乐中的时长单位&#xff0c;但这个时长单位有点特殊&#xff0c;它并不是完全绝对的某一个时间&#xff0c;而正是因为如此&#xff0c;所以不能用 秒 之类的&#xff0c;已经很确定很绝对的时间单位…

C++手写协程项目(协程实现线程结构体、线程调度器定义,线程挂起、切换、恢复函数,模块测试)

协程结构体定义 之前我们使用linux下协程函数实现了线程切换&#xff0c;使用的是ucontext_t结构体&#xff0c;和基于这个结构体的四个函数。现在我们要用这些工具来实现我们自己的一个线程结构体&#xff0c;并实现线程调度和线程切换、挂起。 首先我们来实现以下线程结构体…

C语言自定义类型枚举、枚举类型的定义、枚举的特点、以及自定义类型联合体、联合类型的定义、联合的特点、联合大小的计算、联合判断大小端 的介绍

文章目录 前言一、枚举1. 枚举类型的定义2. 枚举的特点 二、联合&#xff08;共用体&#xff09;1. 联合类型的定义2. 联合的特点3. 联合大小的计算4. 联合体判断大小端1. 不适用联合体判断大小端2. 使用联合体判断大小端 总结 前言 C语言自定义类型枚举、枚举类型的定义、枚举…