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

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...