当前位置: 首页 > news >正文

二叉树的最大深度[简单]

在这里插入图片描述

优质博文:IT-BLOG-CN

一、题目

给定一个二叉树root,返回其最大深度。

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1:

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

示例 2:
输入:root = [1,null,2]
输出:2

树中节点的数量在[0, 104]区间内。
-100 <= Node.val <= 100

二、代码

【1】深度优先搜索: 如果我们知道了左子树和右子树的最大深度lr,那么该二叉树的最大深度即为max(l,r)+1。而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言,在计算当前二叉树的最大深度时,可以先递归计算出其左子树和右子树的最大深度,然后在O(1)时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。

/*** 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 maxDepth(TreeNode root) {// 递归计算数的深度,确定递归的推出条件if (root == null) {return 0;} else {int leftHight = maxDepth(root.left);int rightHight = maxDepth(root.right);return Math.max(leftHight,rightHight) + 1;}}
}

复杂度分析:
1、时间复杂度: O(n)其中n为二叉树节点的个数。每个节点在递归中只被遍历一次。
2、空间复杂度: O(height)其中height表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度。

【2】广度优先搜索: 我们也可以用「广度优先搜索」的方法来解决这道题目,但我们需要对其进行一些修改,此时我们广度优先搜索的队列里存放的是当前层的所有节点。每次拓展下一层的时候,不同于广度优先搜索的每次只从队列里拿出一个节点,我们需要将队列里的所有节点都拿出来进行拓展,这样能保证每次拓展完的时候队列里存放的是当前层的所有节点,即我们是一层一层地进行拓展,最后我们用一个变量ans来维护拓展的次数,该二叉树的最大深度即为ans

/*** 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 maxDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<TreeNode>();// 先存放root节点queue.offer(root);// 总长度int maxLen = 0;// 开启循环,并确定退出循环的条件while (!queue.isEmpty()) {// 获取当前队列的长度,确定该层遍历的次数int size = queue.size();// 我们需要遍历当前层的所有 treeNode// 确定循环条件,并确定退出条件while (size > 0) {TreeNode treeNode = queue.poll();if (treeNode.left != null) {// 注意:添加的时左节点,而不是当前节点queue.offer(treeNode.left);}if (treeNode.right != null) {queue.offer(treeNode.right);}--size;}++maxLen;}return maxLen;}
}

复杂度分析:
1、时间复杂度: O(n)其中n为二叉树的节点个数。与方法一同样的分析,每个节点只会被访问一次。
2、空间复杂度: 此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到O(n)

相关文章:

二叉树的最大深度[简单]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给定一个二叉树root&#xff0c;返回其最大深度。 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3 示例 2&#xff1a…...

[Redis]不同系统间安装redis服务器

日常服务器端开发&#xff0c;消息队列等需求&#xff0c;免不了用到redis&#xff0c;搭建一个redis服务器&#xff0c;方便开发和测试&#xff0c;我们从以下三类系统来说明下&#xff1a; 安装 Redis 服务器的过程因操作系统而异。以下是在常见的 Linux 发行版&#xff08;…...

Unity之动画和角色控制

目录 &#x1f4d5; 一、动画 1.创建最简单的动画 2.动画控制器 &#x1f4d5;二、把动画和角色控制相结合 &#x1f4d5;三、实现实例 3.1 鼠标控制角色视角旋转 3.2 拖尾效果 &#x1f4d5;四、混合动画 最近学到动画了&#xff0c;顺便把之前创建的地形&#xff0…...

C语言库函数实现字符串转大小写

目录 引言 代码 引言 处理字符串时&#xff0c;除了将字符串中的所有大写字母转换为小写字母外&#xff0c;我们还可以利用其他相关函数进行更丰富的文本操作。本文将以一段使用isupper()、tolower()函数实现字符串全转小写的C语言程序为例&#xff0c;详细介绍这两个函数以及…...

hcip----ospf

一&#xff1a;动态路由协议 IGP 协议---RIP OSPF ISIS EIGRP EGP--EGP ---BGP 三个角度的评判一款动态路由协议的优劣 RIP --request response 1.选路--选路依据不好&#xff0c;可能出现环路 2.收敛速度--计时器 3.占用资源-- RIPV1 RIPV2 RIPNG--ipv6 OSPFV1 OSPFV…...

vue中如何写过滤器

全局注册 (可以在main.js中进行全局注册 vue.fifler(test’&#xff0c;function(v){return v0? ‘终止’&#xff1a;v1?进行中:异常 })在组件页面使用 <view>{{state|test}}</view> <script> export default {data(){return {state: 1// state 1 进行中…...

c语言-文件的读写操作(下)

文章目录 前言一、文件的随机读写1.1 fseek()1.2 ftell()1.3 rewind() 总结 前言 本篇文章介绍c语言中文件的随机读写 一、文件的随机读写 1.1 fseek() fseek()函数的作用是根据文件指针的位置和偏移量定位文件指针 int fseek ( FILE * stream, long int offset, int origi…...

android学习笔记----SQLite数据库

用SQLite语句执行&#xff1a; 首先看到界面&#xff1a; 代码如下&#xff1a; MainActivity.java import android.support.v7.app.AppCompatActivity; import android.os.Bundle; import android.text.TextUtils; import android.view.View; import android.widget.EditTe…...

开发知识点-Flutter移动应用开发

支持 安卓 IOS Android 鸿蒙 第一章dart基础章节介绍 移动电商——Flutter-广告Banner组件制作 移动电商——Flutter实战课程介绍 Flutter实例——路由跳转的动画效果...

视频尺寸魔方:分层遮掩3D扩散模型在视频尺寸延展的应用

▐ 摘要 视频延展(Video Outpainting)是对视频的边界进行扩展的任务。与图像延展不同&#xff0c;视频延展需要考虑到填充区域的时序一致性&#xff0c;这使得问题更具挑战性。在本文中&#xff0c;我们介绍了一个新颖的基于扩散模型的视频尺寸延展方法——分层遮掩3D扩散模型(…...

openssl3.2/test/certs - 061 - other@good.org not permitted by CA1

文章目录 openssl3.2/test/certs - 061 - othergood.org not permitted by CA1概述笔记END openssl3.2/test/certs - 061 - othergood.org not permitted by CA1 概述 openssl3.2 - 官方demo学习 - test - certs 笔记 /*! * \file D:\my_dev\my_local_git_prj\study\openSS…...

如何实现无公网ip远程访问本地websocket服务端【内网穿透】

文章目录 1. Java 服务端demo环境2. 在pom文件引入第三包封装的netty框架maven坐标3. 创建服务端,以接口模式调用,方便外部调用4. 启动服务,出现以下信息表示启动成功,暴露端口默认99995. 创建隧道映射内网端口6. 查看状态->在线隧道,复制所创建隧道的公网地址加端口号7. 以…...

pip清华源怎么换回来

怎么临时使用清华源 pip install scrapy -i https://pypi.Python.org/simple/怎么永久换源 pip config set global.index-url https://pypi.tuna.tsinghua.edu.cn/simple修改清华源后怎么换回来 删掉/home/XXX/.config/pip/pip.conf...

[Go]认识Beego框架

对比Gin的简洁&#xff0c;自己之前基于Gin撸了一个架子&#xff0c;确实比beego目录看着舒服多了&#xff0c;不过最近接触到beego的项目&#xff0c;beego的bee工具使用还是很方便&#xff0c;来简单梳理下细节&#xff1b; Beego是一个开源的Go语言Web应用框架&#xff0c;…...

JWT登录

JWT JSON Web Token&#xff08;JSON Web令牌&#xff09; 是一个开放标准(rfc7519)&#xff0c;它定义了一种紧凑的、自包含的方式&#xff0c;用于在各方之间以JSON对象安全地传输信息。此信息可以验证和信任&#xff0c;因为它是数字签名的。jwt可以使用秘密〈使用HNAC算法…...

MySQL和Redis的事务有什么异同?

MySQL和Redis是两种不同类型的数据库管理系统&#xff0c;它们在事务处理方面有一些重要的异同点。 MySQL事务&#xff1a; ACID属性&#xff1a; MySQL是一个关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;支持ACID属性&#xff0c;即原子性&#xff08;Ato…...

【C#】基础巩固

最近写代码的时候各种灵感勃发&#xff0c;有了灵感&#xff0c;就该实现了&#xff0c;可是&#xff0c;实现起来有些不流畅&#xff0c;总是有这样&#xff0c;那样的卡壳&#xff0c;总结下来发现了几个问题。 1、C#基础内容不是特别牢靠&#xff0c;理解的不到位&#xff…...

基于Skywalking开发分布式监控(一)

接手为微服务系统搞链路监控项目一年多&#xff0c;也和skywalking打了一年多的交道&#xff0c;也应该有个总结&#xff0c;主要谈一下搭建监控系统遇到的难点和解决方案。 说明&#xff1a; 本文的代码均由本地演示代码替代&#xff0c;非实际代码 为啥选skywalking&#xf…...

高防服务器什么意思

高防服务器什么意思&#xff0c;为什么要用高防服务器&#xff0c;小编为您整理发布高防服务器什么意思的解读。 高防服务器是指具备较高防御能力的服务器&#xff0c;能够抵御DDoS/CC等网络攻击。 高防服务器通常用于保护游戏、APP、金融、电商等业务&#xff0c;这些领域因为…...

C/C++ - Auto Reference

目录 auto Reference auto 当使用auto​​关键字声明变量时&#xff0c;C编译器会根据变量的初始化表达式推断出变量的类型。 自动类型推断&#xff1a;auto​​关键字用于自动推断变量的类型&#xff0c;使得变量的类型可以根据初始化表达式进行推导。 初始化表达式&#x…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...