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: 功能:通过与企业相关数据库进行…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
