力扣每日一题111:二叉树的最小深度

news/2024/5/19 18:15:34

题目

简单

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

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

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

示例 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.mrgr.cn/p/04125346

相关文章

小程序地理位置接口权限直接抄作业

小程序地理位置接口有什么功能&#xff1f; 随着小程序生态的发展&#xff0c;越来越多的小程序开发者会通过官方提供的自带接口来给用户提供便捷的服务。但是当涉及到地理位置接口时&#xff0c;却经常遇到申请驳回的问题&#xff0c;反复修改也无法通过&#xff0c;给的理由也…

RTT I/O设备模型

I/O设备模型 绝大部分的嵌入式系统都包括一些I/O&#xff08;Input/Output&#xff0c;输入/输出&#xff09;设备&#xff0c;例如仪器上的数据显示屏、工业设备上的串口通信、数据采集设备上用于保存数据的Flash或SD卡&#xff0c;以及网络设备的以太网接口等&#xff0c;都…

TCP的特性(4)

TCP特性 拥塞控制(可靠性机制)延迟应答(效率机制)捎带应答(效率机制)面向字节流(粘包问题)TCP异常机制(心跳包)小结 拥塞控制(可靠性机制) 虽然TCP引入了滑动窗口,能够高效可靠的传输大量数据,但是在开始阶段就发送大量数据,可能引起一系列问题. TCP引入了慢启动机制,先发少量的…

Vue3+.NET6前后端分离式管理后台实战(十七)

1&#xff0c;Vue3.NET6前后端分离式管理后台实战(十七)已经在微信公众号更新&#xff0c;有兴趣的扫码关注一起交流学习。

Learning GitHub Actions Automation and Integration of CI/CD with GitHub【7】

CHAPTER 7 Managing Data Within Workflows 今天,很少有人用一个工作或项目来完成一套完整的工作。考虑一个典型的CI/CD管道。 你通常会有一个做建筑的工作,一个做包装的工作,多个做测试的工作,等等。 但即使这些都是单独的作业,它们仍然需要能够在它们之间传递数据和文件…

Learning GitHub Actions Automation and Integration of CI/CD with GitHub【8】

CHAPTER 8:Managing Workflow Execution 根据定义,GitHub操作工作流更多的是声明性的,而不是命令式的。 这意味着,您不是编写定义如何完成任务的编程逻辑,而是主要通过声明要使用的triggers、jobs、steps和runners来创建工作流。 并且,对于每个步骤,您将定义运行哪些操作…

Learning GitHub Actions Automation and Integration of CI/CD with GitHub【9】

CHAPTER 9:Actions and Security 正如前面几章所看到的,动作提供了令人印象深刻的自动信息水平。 它们还提供了直接在GitHub中完成任务的方法,否则这是不可能的。 然而,这些同样的功能也可能意味着必须事先考虑和计划的安全风险。 否则,您将打开存储库到多个攻击面和漏洞。…

知识图谱在提升大语言模型性能中的应用:减少幻觉与增强推理的综述

幻觉现象指的是模型在生成文本时可能会产生一些听起来合理但实际上并不准确或相关的输出&#xff0c;这主要是由于模型在训练数据中存在知识盲区所致。 为了解决这一问题&#xff0c;研究人员采取了多种策略&#xff0c;其中包括利用知识图谱作为外部信息源。知识图谱通过将信息…

Learning GitHub Actions Automation and Integration of CI/CD with GitHub【4】

CHAPTER 4 : Working with Workflows 我相信您现在已经收集到了,工作流是使用GitHub操作的核心。 我已经介绍了一些理解工作流的基本知识。 但是,您还需要能够轻松地创建、运行和监控它们的成功/失败。 本章将重点介绍这些活动。 首先,我将调查GitHub为从启动程序创建工作流…

Learning GitHub Actions Automation and Integration of CI/CD with GitHub【5】

CHAPTER 5:Runners 无论使用GitHub操作实现什么功能,都必须有一个地方来执行该功能 -- 一个具有足够资源来处理作业的虚拟或物理系统,以及一个配置为在分派作业时与操作控制平面交互的系统。 在操作术语中,在工作流中执行作业的系统被称为运行器。 在高级,跑步器系统有两种…

快速入门!学习鸿蒙App开发的终极指南!

鸿蒙&#xff08;HarmonyOS&#xff09;是华为推出的一款分布式操作系统&#xff0c;旨在为不同设备提供统一的操作体验。鸿蒙App开发可以让应用程序在多个设备上实现流畅运行。本文将介绍鸿蒙App开发的终极指南&#xff0c;帮助您快速入门。 开发环境搭建 鸿蒙App开发过程需要…

Learning GitHub Actions Automation and Integration of CI/CD with GitHub【1】

Foreword 连续集成/连续交付的基本概念(CI/CD)现在已经存在了几十年,因为马丁福勒和马修Foem- mel的作品首次推广CI在2000年9月的开创性的文章,和杰兹谦虚和戴夫法利写了CD在2010年的书连续交付:可靠的软件发布通过构建、测试和部署自动化(艾迪森-韦斯利专业)。然而,CI…

Learning GitHub Actions Automation and Integration of CI/CD with GitHub【2】

CHAPTER 2 : How Does Actions Work❓ 在第一章中,您高度了解了GitHub操作的整体框架和价值。 在本章中,我们将深入研究组成GitHub操作的部分,以及它们如何一起工作,意味着什么启动它们,当它们运行时发生什么,等等。 提醒一下,在GitHub操作的世界中,操作可以参考以下内…

数据结构十一:数组相关经典面试题

本篇博客详细介绍分析数组/顺序表常见的面试题&#xff0c;对于前面所学知识进行一个巩固&#xff0c;同时介绍一些力扣刷题中的一些概念&#xff1a;如&#xff1a;输出型参数等&#xff0c;在刷题中培养自己的编程思维&#xff0c;掌握常见的编程套路&#xff0c;形成题感&am…

智慧农场系统 搭建重点,会用到哪些三方服务?

智慧农场小游戏的搭建重点主要集中在游戏设计、用户体验、数据安全和稳定性等方面。为了实现这些目标&#xff0c;可能会用到以下第三方服务&#xff1a; 游戏引擎和开发工具&#xff1a;使用成熟的游戏引擎和开发工具可以极大地简化开发流程&#xff0c;提高开发效率。例如&a…

M2 Mac mini跑Llama3

前言 在4-19左右&#xff0c;Meta 宣布正式推出下一代开源大语言模型 Llama 3&#xff1b;共包括 80 亿和 700 亿参数两种版本&#xff0c;号称 “是 Llama 2 的重大飞跃”&#xff0c;并为这些规模的 LLM 确立了新的标准。实际上笔者早就体验过&#xff0c;只不过自己电脑没什…

【华为】路由策略小实验

【华为】软考中级-路由策略实验 实验需求拓扑配置AR1AR2需求1需求2 AR3 检验 实验需求 1、让 R3 可以学到R1的 192.168.10.0/24和192.168.20.0/24的 路由&#xff0c;不能学到192.168.30.0/24。 2、让 R1可以学到 R3 的 172.16.20.0/24和172.16.30.0/24的路由&#xff0c;不能…

Android手写自己的路由SDK

实现自己的路由框架 ​ 在较大型的Android app中常会用到组件化技术&#xff0c;针对不同的业务/基础功能对模块进行划分&#xff0c;从上到下为壳工程、业务模块、基础模块。其中业务模块依赖基础模块&#xff0c;壳工程依赖业务模块。同级的横向模块&#xff08;比如多个业务…

iMazing下载安装不了怎么办?

iMazing是一款可用于iPhone、iPad等ios移动设备管理软件&#xff0c;但需要注意的是&#xff0c;iMazing只能安装在Windows与Mac系统中&#xff0c;不能安装在iOS移动设备上。iOS移动设备可以通过USB线或Wi-Fi连接Windows或Mac系统上的iMazing软件。 iMazing的安装失败&#x…

手撕spring框架(3)

手撕spring框架&#xff08;3&#xff09; 相关系列 手撕spring框架&#xff08;1&#xff09; 手撕spring框架&#xff08;2&#xff09; 手撕spring框架&#xff08;4&#xff09; InitializingBean 接口详解 什么是 InitializingBean 接口&#xff1f; InitializingBean 接…