leetcode 二叉树的最大深度

104. 二叉树的最大深度

已解答

简单

相关标签

相关企业

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

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

示例 1:

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

示例 2:

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

提示:

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

 方法一:后序遍历(DFS)

思路

  1. 使用递归方法计算二叉树的最大深度。
  2. 二叉树的最大深度可以表示为:
    • 如果节点为空(即 root == None),那么深度为 0。
    • 否则,树的最大深度为左子树和右子树的最大深度加 1。
  3. 递归地计算左右子树的深度,并返回它们的最大值加 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{return Math.max(maxDepth(root.left),maxDepth(root.right))+1;}}
}

思路与算法

如果我们知道了左子树和右子树的最大深度 l 和 r,那么该二叉树的最大深度即为

max(l,r)+1

复杂度分析

  • 时间复杂度:O(N),其中 N 是二叉树中的节点数。因为我们每个节点都需要访问一次。
  • 空间复杂度:O(H),其中 H 是二叉树的高度。在最坏情况下(树完全倾斜),递归栈的深度可能会达到树的高度。

示例

对于输入 root = [3,9,20,null,null,15,7]

  1. 根节点 3 的左子树深度为 1,右子树深度为 2。
  2. 因此,最大深度为 2 + 1 = 3
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:# 如果节点为空,深度为 0if root is None:return 0# 递归求左右子树的深度left_depth = self.maxDepth(root.left)right_depth = self.maxDepth(root.right)# 返回左右子树较大深度加 1return max(left_depth, right_depth) + 1

方法 2:迭代 DFS(使用栈)

可以用栈来实现 DFS,从根节点开始,将每个节点和对应的深度存入栈中,然后更新最大深度。

代码如下:

class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:# 特殊情况处理if root is None:return 0# 使用栈来进行 DFS,每个元素是 (节点, 深度)stack = [(root, 1)]max_depth = 0# 开始 DFSwhile stack:node, depth = stack.pop()if node:# 更新最大深度max_depth = max(max_depth, depth)# 将左右子节点及其深度加入栈stack.append((node.left, depth + 1))stack.append((node.right, depth + 1))return max_depth

方法二:层序遍历(BFS)

树的层序遍历 / 广度优先搜索往往利用 队列 实现。

关键点: 每遍历一层,则计数器 +1 ,直到遍历完成,则可得到树的深度。

在计算二叉树的最大深度时,我们也可以使用广度优先搜索(BFS)来实现。BFS 会按层遍历二叉树,因此每遍历完一层,深度就增加 1。使用 BFS 的优点是,它逐层访问节点,可以在找到最远叶子节点时直接得出最大深度。

  1. 从根节点开始,将其加入队列,并初始化深度为 0。
  2. 每一层的节点都会被处理,并在遍历该层的所有节点后,深度增加 1。
  3. 当队列为空时,说明所有层都遍历完了,此时的深度就是树的最大深度。

代码实现

以下是 BFS 的实现代码,使用 Python 的 collections.deque 来实现队列操作:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:# 如果根节点为空,直接返回深度 0if root is None:return 0# 初始化队列并将根节点加入队列queue = deque([root])depth = 0# 开始 BFSwhile queue:# 每一层的节点数量level_size = len(queue)# 处理当前层的所有节点for _ in range(level_size):node = queue.popleft()# 将子节点加入队列if node.left:queue.append(node.left)if node.right:queue.append(node.right)# 当前层处理完,深度加 1depth += 1return depth

复杂度分析

  • 时间复杂度:O(N),其中 N 是节点数。每个节点访问一次。
  • 空间复杂度:O(W),其中 W 是树的最大宽度。在最坏情况下,队列中最多会存储一层的所有节点数量。

示例

对于输入 root = [3,9,20,null,null,15,7]

  1. 第一层只有根节点 3,深度为 1。
  2. 第二层有节点 920,深度增加到 2。
  3. 第三层有节点 157,深度增加到 3。
  4. 遍历完所有层,最终返回深度 3

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/479904.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VMware ubuntu创建共享文件夹与Windows互传文件

1.如图1所示&#xff0c;点击虚拟机&#xff0c;点击设置&#xff1b; 图1 2.如图2所示&#xff0c;点击选项&#xff0c;点击共享文件夹&#xff0c;如图3所示&#xff0c;点击总是启用&#xff0c;点击添加&#xff1b; 图2 图3 3.如图4所示&#xff0c;出现命名共享文件夹…

matlab 实现混沌麻雀搜索算法的光伏MPPT控制仿真

1、内容简介 略 103-可以交流、咨询、答疑 2、内容说明 略 3、仿真分析 略 4、参考论文 略

Unity3D 截图

使用 Unity3D 自带的截图接口&#xff0c;制作截图工具。 截图 有时候我们想对 Unity 的窗口进行截图&#xff0c;如果直接使用一些截图工具&#xff0c;很难截取到一张完整分辨率的图片&#xff08;例如&#xff0c;我们想要截取一张 1920 * 1080 的图片&#xff09;。 其实…

STM32F10x 定时器

使用定时器实现&#xff1a;B5 E5的开关 添加相关的.h路径文件 添加相关的.c配置文件 led.h文件 用于声明LED函数 #ifndef __LED_H //没有定义__LED_H #define __LED_H //就定义__LED_H #define LED1_ON GPIO_ResetBits(GPIOB,GPIO_Pin_5) #defi…

PMP好考吗,有多大的价值?

非常好考&#xff01;PMP目前大陆地区的笔试是只有选择题的&#xff0c;运气好的话 蒙一个都能对&#xff0c;所以PMP的通过率高&#xff0c;这也是很多人考了吐槽PMP没用&#xff0c;是“水证”&#xff0c;但是每年考PMP 的人不减反增&#xff0c;大家可以想一下&#xff0c;…

css:项目

这是一个完整的网站制作的流程 美工会先制作一个原型图&#xff1a; 原型图写的不详细&#xff0c;就是体现一个网页大致的布局 然后美工再做一个psd样例图片 然后再交给程序员 项目 模块化开发&#xff1a;把代码的不同的样式封装起来&#xff0c;需要用到相同样式的标签就…

VsCode 插件推荐(个人常用)

VsCode 插件推荐&#xff08;个人常用&#xff09;

黑马程序员Java项目实战《苍穹外卖》Day01

苍穹外卖-day01 课程内容 软件开发整体介绍苍穹外卖项目介绍开发环境搭建导入接口文档Swagger 项目整体效果展示&#xff1a; ​ 管理端-外卖商家使用 ​ 用户端-点餐用户使用 当我们完成该项目的学习&#xff0c;可以培养以下能力&#xff1a; 1. 软件开发整体介绍 作为一…

Python双向链表、循环链表、栈

一、双向链表 1.作用 双向链表也叫双面链表。 对于单向链表而言。只能通过头节点或者第一个节点出发&#xff0c;单向的访问后继节点&#xff0c;每个节点只能记录其后继节点的信息&#xff08;位置&#xff09;&#xff0c;不能向前遍历。 所以引入双向链表&#xff0c;双…

k8s网络服务

k8s 中向外界提供服务的几种方法port-forward、NodePort&#xff0c;以及 更加常用的提供服务的资源ingress。 1 kubectl port-forward service/redis 6379:6379 现在k8s中有一个pod运行在6379&#xff0c;本机访问映射到6379上&#xff0c;它可以针对部署&#xff0c;服务&…

eduSRC挖洞思路

声明 学习视频来自 B 站UP主泷羽sec&#xff0c;如涉及侵权马上删除文章。 笔记的只是方便各位师傅学习知识&#xff0c;以下网站只涉及学习内容&#xff0c;其他的都与本人无关&#xff0c;切莫逾越法律红线&#xff0c;否则后果自负。 ✍&#x1f3fb;作者简介&#xff1a;致…

Leetcode - 周赛424

目录 一&#xff0c;3354. 使数组元素等于零 二&#xff0c; 3355. 零数组变换 I 三&#xff0c;3356. 零数组变换 II 四&#xff0c;3357. 最小化相邻元素的最大差值 一&#xff0c;3354. 使数组元素等于零 本题实际上是一个前/后缀和的问题&#xff0c;就是判断前缀和与后…

Vue2中 vuex 的使用

1.安装 vuex 安装vuex与vue-router类似&#xff0c;vuex是一个独立存在的插件&#xff0c;如果脚手架初始化没有选 vuex&#xff0c;就需要额外安装。 yarn add vuex3 或者 npm i vuex3 233 Vue2 Vue-Router3 Vuex3 344 Vue3 Vue-Router4 Vuex4 2. 新建 store/index.j…

数据结构C语言描述5(图文结合)--队列,数组、链式、优先队列的实现

前言 这个专栏将会用纯C实现常用的数据结构和简单的算法&#xff1b;有C基础即可跟着学习&#xff0c;代码均可运行&#xff1b;准备考研的也可跟着写&#xff0c;个人感觉&#xff0c;如果时间充裕&#xff0c;手写一遍比看书、刷题管用很多&#xff0c;这也是本人采用纯C语言…

Windows修复SSL/TLS协议信息泄露漏洞(CVE-2016-2183) --亲测

漏洞说明&#xff1a; 打开链接&#xff1a;https://docs.microsoft.com/zh-cn/troubleshoot/windows-server/windows-security/restrict-cryptographic-algorithms-protocols-schannel 可以看到&#xff1a; 找到&#xff1a;应通过配置密码套件顺序来控制 TLS/SSL 密码 我们…

深度学习图像视觉 RKNN Toolkit2 部署 RK3588S边缘端 过程全记录

深度学习图像视觉 RKNN Toolkit2 部署 RK3588S边缘端 过程全记录 认识RKNN Toolkit2 工程文件学习路线&#xff1a; Anaconda Miniconda安装.condarc 文件配置镜像源自定义conda虚拟环境路径创建Conda虚拟环境 本地训练环境本地转换环境安装 RKNN-Toolkit2&#xff1a;添加 lin…

controller中的参数注解@Param @RequestParam和@RequestBody的不同

现在controller中有个方法&#xff1a;&#xff08;LoginUserRequest是一个用户类对象&#xff09; PostMapping("/test/phone")public Result validPhone(LoginUserRequest loginUserRequest) {return Result.success(loginUserRequest);}现在讨论Param("login…

Android按键点击事件三种实现方法

1. 在xml文件中为 Button 添加android:onclick属性 由于没有onclick这个函数&#xff0c;onclick下面会提示红色波浪线错误&#xff0c;然后单击一下"onclick"按住键盘上AltEnter键,选择在activity中生成函数 public void onclick(View view) {Toast.makeText(this,&…

全景图像(Panorama Image)向透视图像(Perspective Image)的跨视图转化(Cross-view)

一、概念讲解 全景图像到透视图像的转化是一个复杂的图像处理过程&#xff0c;它涉及到将一个360度的全景图像转换为一个具有透视效果的图像&#xff0c;这种图像更接近于人眼观察世界的方式。全景图像通常是一个矩形图像&#xff0c;它通过将球面图像映射到平面上得到&#xf…

RabbitMQ7:消息转换器

欢迎来到“雪碧聊技术”CSDN博客&#xff01; 在这里&#xff0c;您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者&#xff0c;还是具有一定经验的开发者&#xff0c;相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导&#xff0c;我将…