当前位置: 首页 > 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…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...