python-leetcode 36.二叉树的最大深度
题目:
给定一个二叉树root,返回其最大深度
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数

方法一:深度优先搜索
知道了左子树和右子树的最大深度l和r,那么该二叉树的最大深度即为:max(l,r)+1
而左子树和右子树的最大深度又可以以同样的方式进行计算。因此可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言,在计算当前二叉树的最大深度时,可以先递归计算出其左子树和右子树的最大深度,然后在O(1)时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def maxDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if root is None:return 0else:left_height=self.maxDepth(root.left)right_height=self.maxDepth(root.right)return max(left_height,right_height)+1
时间复杂度:O(n)n为二叉树节点的个数。每个节点在递归中只被遍历一次。
空间复杂度:O(height)其中height表示二叉树的高度
方法二:广度优先搜索
广度优先搜索的队列里存放的是「当前层的所有节点」。每次拓展下一层的时候,用一个变量ans来维护拓展的次数,该二叉树的最大深度即为ans。

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def maxDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0queue=[root] #使用一个队列(queue)来进行广度优先搜索, 初始时包含根节点 ans=0while queue: #在队列不为空时持续进行。每次循环表示遍历树的一层size=len(queue) #获取当前队列中节点的数量,即当前层的节点数while size>0:node=queue.pop(0)if node.left:queue.append(node.left) #当前节点 node 有左子节点,就将左子节点加入队列if node.right:queue.append(node.right)#当前节点 node 有右子节点,就将右子节点加入队列size-=1 #处理完当前节点,减少层内节点计数ans+=1 #层处理完,增加深度计数器return ans
时间复杂度:O(n)每个节点只会被访问一次
空间复杂度:O(n)取决于队列存储的元素数量
源自力扣官方题解
相关文章:
python-leetcode 36.二叉树的最大深度
题目: 给定一个二叉树root,返回其最大深度 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数 方法一:深度优先搜索 知道了左子树和右子树的最大深度l和r,那么该二叉树的最大深度即为:max(l,r)1 而左子树和右子树的最大深…...
MySQL事务的特性和隔离级别
一、事务的特性 事务是一组操作的集合,它是一个不可分割的工作单位,事务会把所有的操作作为一个整体一起向系统提交或撤销操作,即这些操作要么同时成功,要么同时失败 事务的有以下四个特性(acid)…...
Oracle视图(基本使用)
视图 视图是通过定制的方式显示一个或者多个表的数据。 视图可以视为“虚拟表”或“存储的查询”。 视图的优点: 提供了另外一种级别的表安全性隐藏了数据的复杂性简化了用户的SQL命令隔离基表结构的改变通过重命名列,从另一个角度提供数据。 视图里…...
C++ Primer 类的作用域
欢迎阅读我的 【CPrimer】专栏 专栏简介:本专栏主要面向C初学者,解释C的一些基本概念和基础语言特性,涉及C标准库的用法,面向对象特性,泛型特性高级用法。通过使用标准库中定义的抽象设施,使你更加适应高级…...
【学习笔记】Cadence电子设计全流程(二)原理图库的创建与设计(上)
【学习笔记】Cadence电子设计全流程(二)原理图库的创建与设计(上) 2.1 OrCAD X Capture 界面预览2.2 原理图元件符号的组成2.3 原理图库的创建和元件的创建2.4 以 STM32F103T8U6 芯片为例创建元件 全部内容见专栏:【Ca…...
学习数据结构(11)二叉树(堆)下
1.堆的概念 如果有⼀个集合 K {k0,k1,k2,...,k(n-1)} ,把它的所有元素按完全二叉树的形式存储在一个一维数组中,并满足:K(i)<2*i1且K(i)<2*i2(K(i)>2*i1且K(i)>2*i2&a…...
HarmonyOS NEXT网络状态监听HTTP和RCP请求网络
当我们在HarmonyOS NEXT中开发的应用,基本上都会使用网络请求,从服务端获取数据在客户端显示或者供用户交互,有时候网络发生变化时,我们需要做一些相应的操作,接下来我们一起来了解下在HarmonyOS NEXT下如何监听网络状…...
MySQL数据库(4)—— 数据类型
目录 一,数据类型分类 二,数值类型 2.1 tinyint类型 2.2 bit类型 2.3 float类型 2.4 decimal类型 三,字符串类型 3.1 char类型 3.2 varchar类型 四,时间日期类型 五,enum和set类型 5.1 基本使用 5.2 解释查…...
如何在Odoo 18中创建记录规则Rule
如何在Odoo 18中创建记录规则Rule 记录规则是管理访问控制的关键,它能让你依据用户角色,定义谁可以在系统内查看、创建或修改特定记录。例如,公司中的普通员工只能查看或修改与与自己直接相关的数据,而经理则有权限访问和编辑所有…...
petalinux高版本设置自动登录和开机自启动配置
petalinux-config -c rootfs 依次选择 Image Features -> serial-autologin-root 这是配置 进来就是root权限 创建并安装名为 myapp-init 的新建应用程序 petalinux-create -t apps --template install -n myapp-init --enable 编辑 project-spec/meta-user/recipes-…...
操作系统2.4
一、死锁,饥饿,死循环 死锁:各进程互相等待对方手里的资源,导致各进程都阻塞,无法向前推进的现象 饥饿:由于长期得不到想要的资源,某进程无法向前推进的现象,例如:短进…...
Springboot + Ollama + IDEA + DeepSeek 搭建本地deepseek简单调用示例
1. 版本说明 springboot 版本 3.3.8 Java 版本 17 spring-ai 版本 1.0.0-M5 deepseek 模型 deepseek-r1:7b 需要注意一下Ollama的使用版本: 2. springboot项目搭建 可以集成在自己的项目里,也可以到 spring.io 生成一个项目 生成的话,如下…...
解析DrugBank数据库数据|Python
一、DrugBank 数据库简介 DrugBank 是一个综合性的生物信息学和化学信息学数据库,专门收录药物和靶点的详细信息。它由加拿大阿尔伯塔大学的 Wishart 研究组 维护,提供化学、药理学、相互作用、代谢、靶点等多方面的药物数据。DrugBank 结合了实验数据和…...
CUDA Toolkit 历史版本 cuda安装
cuda安装 CUDA Toolkit 版本选择1. NVIDIA-SMI 525.60.11静默安装2. CUDA Toolkit 12.6.0 安装禁用 nouveau依赖安装下载安装 cuda显卡驱动安装成功设置环境变量 3. 安装失败切换到多用户文本模式 参考 CUDA Toolkit 版本选择 CUDA Toolkit 历史版本 1. NVIDIA-SMI 525.60.11 …...
Aseprite详细使用教程(12)——轮廓工具和多边形工具
一、轮廓工具 (1)核心功能 轮廓生成:给鼠标起点和终点的连线以及两点经过的路径形成的轮廓,可单独指定轮廓颜色。 (2) 使用方法 选择工具后,鼠标左键点击,按住不松手,拖动…...
macos sequoia 禁用 ctrl+enter 打开鼠标右键菜单功能
macos sequoia默认ctrlenter会打开鼠标右键菜单,使得很多软件有冲突。关闭方法: end...
分布式架构与XXL-JOB
目录 先了解什么是任务调度? 什么是分布式任务调度? 了解XXL-JOB分布式任务调度平台 如何搭建XXL-JOB? 分片广播 作业分片方案 最近学习在项目的媒资管理模块如何高效处理大量视频,上传单个视频可能涉及到转码,…...
leetcode day18 移除元素 26+283
26 删除有序数组中的重复项 给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元…...
【HarmonyOS Next】鸿蒙监听手机按键
【HarmonyOS Next】鸿蒙监听手机按键 一、前言 应用开发中我们会遇到监听用户实体按键,或者扩展按键的需求。亦或者是在某些场景下,禁止用户按下某些按键的业务需求。 这两种需求,鸿蒙都提供了对应的监听事件进行处理。 onKeyEvent 默认的…...
用Deepseek查询快证API-物流查询-实名认证-企业实名认证
快证API可能是一个提供多种验证和查询服务的平台,包括但不限于企业实名认证、短链接生成、手机号归属地查询、IP地址查询等。以下是根据搜索结果整理的关于快证API的相关信息: 企业实名认证API: 功能:通过与企业相关数据库进行…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
