力扣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

方法一:深度优先搜索 思路及解法
首先可以想到使用深度优先搜索的方法,遍历整棵树,记录最小深度。
对于每一个非叶子节点,我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题,可以递归地解决该问题。

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

复杂度分析

时间复杂度:O(N),其中 N 是树的节点数。对每个节点访问一次。

空间复杂度:O(H),其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关,空间复杂度为 O(log⁡N)。

方法二:广度优先搜索 思路及解法 同样,我们可以想到使用广度优先搜索的方法,遍历整棵树。
当我们找到一个叶子节点时,直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。

class Solution {
    class QueueNode {
        TreeNode node;
        int depth;

        public QueueNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<QueueNode> queue = new LinkedList<QueueNode>();
        queue.offer(new QueueNode(root, 1));
        while (!queue.isEmpty()) {
            QueueNode nodeDepth = queue.poll();
            TreeNode node = nodeDepth.node;
            int depth = nodeDepth.depth;
            if (node.left == null && node.right == null) {
                return depth;
            }
            if (node.left != null) {
                queue.offer(new QueueNode(node.left, depth + 1));
            }
            if (node.right != null) {
                queue.offer(new QueueNode(node.right, depth + 1));
            }
        }

        return 0;
    }
}

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

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

相关文章

这样的Python自动化测试面试题,测开来了都不一定都会把!

十、接口自动化 10.1 接口自动化怎么测试 ( Python requestspytest 版本) 原来我们接口自动化是用 python request pytest 执行 接口自动化其实主要就是接口测试的基础上填加了断言&#xff0c;参数化&#xff0c;动态关联 做接口自动化之前&#xff0c;我们也会划分模块&#…

【数据结构】C语言实现堆(附完整运行代码)

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 目录 一.了解项目功能 二.项目功能演示(以大堆为例) 三.逐步实现项目功能模块及其逻辑详解 1.实现堆程序主函数 2.创建堆结构 3.堆的初始化 4.数据元素入堆 5.数据元素…

Linux上编译和测试V8引擎源码

介绍 V8引擎是一款高性能的JavaScript引擎&#xff0c;广泛应用于Chrome浏览器和Node.js等项目中。在本篇博客中&#xff0c;我们将介绍如何在Linux系统上使用depot_tools工具编译和测试V8引擎源码。 步骤一&#xff1a;安装depot_tools depot_tools是一个用于Chromium开发…

边缘智能网关如何应对环境污染难题

随着我国工业化、城镇化的深入推进&#xff0c;包括大气污染在内的环境污染防治压力继续加大。为应对环境污染防治难题&#xff0c;佰马综合边缘计算、物联网、智能感知等技术&#xff0c;基于边缘智能网关打造环境污染实时监测、预警及智能干预方案&#xff0c;可应用于大气保…

【华为OD题库-076】执行时长/GPU算力-Java

题目 为了充分发挥GPU算力&#xff0c;需要尽可能多的将任务交给GPU执行&#xff0c;现在有一个任务数组&#xff0c;数组元素表示在这1秒内新增的任务个数且每秒都有新增任务。 假设GPU最多一次执行n个任务&#xff0c;一次执行耗时1秒&#xff0c;在保证GPU不空闲情况下&…

ELK综合案例

综合案例 ELKfilebeatnginxjson nginx配置 1,在nginx服务器上安装nginx # yum install epel-release # yum install nginx 2,将nginx日志改成json格式,这样各个字段就方便最终在kibana进行画图统计了 # vim /etc/nginx/nginx.conf ​ http {log_format main $remote_ad…

解决Git提交错误分支

如果 Git 提交到错误的分支&#xff0c;可以通过以下步骤将其转移到正确的分支上&#xff1a; 1.检查当前所在的分支&#xff0c;可以通过 git branch 命令查看。 git branch2.切换到正确的分支&#xff0c;可以通过 git checkout <正确的分支名> 命令进行切换。 git …

windows系统proteus中Ardunio Mega 2560和虚拟机上Ubuntu系统CuteCom进行串口通信

在文章利用proteus实现串口助手和arduino Mega 2560的串口通信-CSDN博客 中&#xff0c;实现了windows系统的proteus中Ardunio Mega 2560和SSCOM通过虚拟串口进行通信。虚拟串口的连接示意图如下图所示。 在文章windows系统和虚拟机上ubuntu系统通过虚拟串口进行通信-CSDN博客…

高级网工在Linux服务器抓包,少不了这几条常用的tcpdump命令。

Linux 的命令太多&#xff0c;tcpdump 是一个非常强大的抓包命令。有时候想看线上发生的一些问题&#xff1a; nginx 有没有客户端连接过来…… 客户端连接过来的时候 Post 上来的数据对不对…… 我的 Redis 实例到底是哪些业务在使用…… tcpdump 作为网络分析神器就派上用场…

2023年四川网信人才技能大赛 实操赛Writeup

文章目录 Crypto比base64少的baseaffine简单的RSA Misc不要动我的flagSimpleUSB猜猜我是谁不聪明的AI Pwngetitezbbstack Reverse谁的DNA动了Dont Touch Me Weblittle_gamejustppbezbbssmart 题目附件&#xff0c;文章末尾微信公众号点点关注亲&#xff0c;谢谢亲~ 题目附件链接…

Ubuntu安装TensorRT

文章目录 1. 安装CUDAa. 下载CUDAb. 安装CUDAc. 验证CUDA 2. 安装CUDNNa. 下载CUDNNb. 安装CUDNNc. 验证CUDNN 3. 安装TensorRTa. 下载TensorRTb. 解压TensorRTc. 安装TensorRTd. 安装uff和graphsurgeone. 验证是否安装成功f. 备注 关注公众号&#xff1a;『AI学习星球』 回复&…

机器学习算法性能评估常用指标总结

考虑一个二分问题&#xff0c;即将实例分成正类&#xff08;positive&#xff09;或负类&#xff08;negative&#xff09;。对一个二分问题来说&#xff0c;会出现四种情况。如果一个实例是正类并且也被 预测成正类&#xff0c;即为真正类&#xff08;True positive&#xff0…

Halcon 简单的ORC 字体识别

文章目录 仿射变化识别使用助手自己训练 仿射变化 将图片进行矫正处理 dev_close_window() dev_open_window(0, 0, Width, Height, black, WindowHandle) read_image(Image,C:/Users/Augustine/Desktop/halcon/image.png) *获取图片的大小 get_image_size(Image, Width, Height…

宝塔面板部署Apache服务器搭建本地站点发布到公网可访问【内网穿透】

文章目录 前言1. 环境安装2. 安装cpolar内网穿透3. 内网穿透4. 固定http地址5. 配置二级子域名6. 创建一个测试页面 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家…

什么是HTTP/2?它与HTTP/1.x相比有什么改进?

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…

php 接入 百度编辑器

按照github上的操作下载百度编辑器的包后&#xff0c;根据文档上的步骤操作&#xff08;可能会遇到报错&#xff09;&#xff1a; 1、git clone 仓库 2、npm install 安装依赖&#xff08;如果没有安装 grunt , 请先在全局安装 grunt&#xff09; 我的是报了下面的错&#…

安装Nacos2.2.3集群

目录 一、传统方式安装 二、Docker安装 一、传统方式安装 1、配置jdk环境 vi /etc/profile JAVA_HOME/usr/local/java JRE_HOME/usr/local/java/jre CLASSPATH.:$JAVA_HOME/lib/dt.jar:$JAVA_HOME/lib/tools.jar:$JRE_HOME/lib PATH$JAVA_HOME/bin:$PATH export PATH JAVA_…

windows启动出现 zookeeper此处不应有java

可能是Java 路径出了问题&#xff0c;这个programFiles直接有空格&#xff0c;没错就有空格&#xff0c;笔者一开始以为这么点算什么空格&#xff0c;需要把这个对应的Java文件到别的英文路径下&#xff0c;并且修改环境变量。就可以启动的。 还可以启动方式有很多种&#xff0…

vs vue项目目录说明

vue项目目录结构说明 视图&#xff1a; 主要描述src和依赖配置 src下 assets:存放需要用到的静态资源文件的地方 如css.js.img.view等 commponents:存放一些通用的组件&#xff1b;例&#xff1a;在开发当中如果有需要抽出来的公用模块&#xff0c;可以封装为通用组件&#xf…

【C++】异常 -- 详解

一、C 语言传统的处理错误的方式 传统的错误处理机制&#xff1a; 终止程序&#xff0c;如 assert&#xff0c;缺陷&#xff1a;用户难以接受。如发生内存错误&#xff0c;除 0 错误时就会终止程序。 返回错误码&#xff0c;缺陷&#xff1a;需要程序员自己去查找对应的错误。…