二叉树的最大深度,力扣

目录

题目地址:

题目:

我们直接看题解吧:

快速理解题解小建议:

审题目+事例+提示:

解题方法:

解题方法分析:

方法1后序遍历(DFS)

解题分析:

解题思路:

代码实现:

方法2层序遍历(BFS) 

解题分析:

解题思路:

代码实现:


题目地址:

104. 二叉树的最大深度 - 力扣(LeetCode)

难度:简单

今天刷二叉树的最大深度,大家有兴趣可以点上面链接,看看题目要求,试着做一下。

题目:

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

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

我们直接看题解吧:

快速理解题解小建议:

可以先简单看一下解题思路,然后再照着代码看思路,会更容易理解一些。

审题目+事例+提示:

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

解题方法:

方法1,深度优先搜索(DFS)

方法2,广度优先搜索(BFS)

解题方法分析:

树的遍历方式总体分为两类:深度优先搜索(DFS)、广度优先搜索(BFS)。

常见 DFS : 先序遍历、中序遍历、后序遍历。

相关解题文章链接:

二叉树的前序遍历,力扣-CSDN博客

二叉树的中序遍历,力扣-CSDN博客

二叉树的层序遍历,力扣-CSDN博客

常见 BFS : 层序遍历(即按层遍历)。

相关解题文章链接:

二叉树的层序遍历,力扣-CSDN博客

求树的深度需要遍历树的所有节点,本文将介绍基于 后序遍历(DFS) 和 层序遍历(BFS) 的两种解法。

方法1后序遍历(DFS)

解题分析:

·树的后序遍历 / 深度优先搜索往往利用递归或栈实现,

·本题关键点在于理解此树的深度和其左(右)子树的深度之间的关系

即此树深度等于左子树的深度与右子树的深度中的最大值+1。

解题思路:

1、判断root,节点是否为空,空则返回0

2、进行递归操作:

    ·计算节点root左子树的深度,即调用maxDepth(root.left)

   ·计算节点root右子树的深度,即调用maxDepth(root.right)

3、最后返回左右子树深度最大者+1,即为此树的最大深度。

参考题解: 104. 二叉树的最大深度题解

代码实现:

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;//判断root,节点是否为空,空则返回0
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }//计算节点root左右子树的深度,返回左右子树深度最大者+1
}

方法2层序遍历(BFS) 

解题分析:

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

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

解题思路:

1、判断root节点是否为空,当 root为空,直接返回0 。

2、初始化: 队列 queue (加入根节点 root ),计数器 res = 0。

3、循环遍历: 当 queue 为空时跳出。

       ·初始化一个空列表 tmp ,用于临时存储下一层节点。

      ·遍历队列: 遍历 queue 中的各节点 node ,并将其左子节点和右子节点加入 tmp。

     ·更新队列: 执行 queue = tmp ,将下一层节点赋值给 queue。

     ·统计层数: 执行 res += 1 ,即层数+1。

4、返回值: 返回 res 即可。

参考题解: 104. 二叉树的最大深度题解

代码实现:

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;//判空操作,当 root为空,直接返回0
        List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
        int res = 0;//创建队列queue与计数变量res,以及空列表tmp
        while (!queue.isEmpty()) {//队列为空时退出循环
            tmp = new LinkedList<>();//初始化空列表
            
            for(TreeNode node : queue) {//当前层节点遍历循环
                if (node.left != null)tmp.add(node.left);//左子节点非空则加入 tmp
                if (node.right != null)tmp.add(node.right);//右子节点非空则加入tmp
            }
            queue = tmp;//执行 queue = tmp ,将下一层节点赋值给 queue。
            res++;//res+1,即层数+1
        }
        return res;//返回 res 即可
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

启动 Mac 时显示闪烁的问号

启动 Mac 时显示闪烁的问号 如果启动时在 Mac 屏幕上看到闪烁的问号&#xff0c;这意味着你的 Mac 无法找到自身的系统软件。 如果 Mac 启动时出现闪烁的问号且无法继续启动&#xff0c;请尝试以下步骤。 1.通过按住其电源按钮几秒钟来关闭 Mac。 2.按一下电源按钮&#xf…

强化学习5——动态规划初探

动态规划具体指的是在某些复杂问题中&#xff0c;将问题转化为若干个子问题&#xff0c;并在求解每个子问题的过程中保存已经求解的结果&#xff0c;以便后续使用。实际上动态规划更像是一种通用的思路&#xff0c;而不是具体某个算法。 在强化学习中&#xff0c;被用于求解值函…

华为MDC610接口说明

1、MDC610对外功能接口 2、1、MDC610硬件技术规格

前端插件库-VUE3 使用 vue-codemirror 插件

VUE3 插件 vue-codemirror 使用步骤和实例、基于 CodeMirror &#xff0c;适用于 Vue 的 Web 代码编辑器。 第一步&#xff1a;安装 vue-codemirror & codemirror 包 &#xff0c; 以及语言包 npm install codemirror --save npm install vue-codemirror --savenpm insta…

Linux第13步_安装“vim编辑器”及应用介绍

学习“磁盘重新分区”后&#xff0c;嵌入式Linux系统环境搭建进入安装“vim编辑器”这个环节。vim编辑器可以用来修改文件&#xff0c;在后期使用中&#xff0c;会经常用到。 1、安装“vim编辑器” 输入“sudo apt-get install vim回车”&#xff0c;就可以执行安装“vim编辑…

SpringIOC之support模块ContextTypeMatchClassLoader

博主介绍:✌全网粉丝5W+,全栈开发工程师,从事多年软件开发,在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战,博主也曾写过优秀论文,查重率极低,在这方面有丰富的经验✌ 博主作品:《Java项目案例》主要基于SpringBoot+MyBatis/MyBatis-plus+…

【Bootstrap学习 day11】

Bootstrap5字体图标 字体图标是在Web项目中使用的图标字体。 使用字体图标的好处是&#xff0c;可以通过应用CSS color属性来创建任何颜色的图标。此外&#xff0c;要更改图标的大小&#xff0c;只需使用CSS font-size属性即可。 获取字体图标 在网页中包含Bootstrap5图标的最…

opencv图像金字塔

下采样&#xff1a; #include <opencv2/opencv.hpp> #include <iostream>int main() {// 读取图像cv::Mat src cv::imread("C:/Users/10623/Pictures/adf4d0d56444414cbeb809f0933b9214.png");if (src.empty()) {std::cout << "无法加载图像…

【非关系型数据库】Redis概述及安装、命令使用

目录 前瞻 关系型数据库 非关系型数据库 关系型数据库和非关系型数据库区别 数据存储方式不同 扩展方式不同 对事务性的支持不同 非关系型数据库产生背景 总结 Redis简介 什么是Redis Redis具有的优点 Redis使用场景 哪些数据适合放入缓存中&#xff1f; Redis为什…

nodejs01

nodejs作用 Node.js 是一个免费的、开源的、跨平台的 JavaScript 运行时环境&#xff0c;允许开发人员在浏览器之外编写命令行工具和服务器端脚本. 是javascript的一个运行环境&#xff0c;&#xff0c;&#xff0c; nodejs stream 是前端工程化的基础 nodejs可以作为中间层&…

南金研小巧的CAN总线记录仪在冬测中的使用

南金研小巧的CAN总线记录仪在冬测中的使用&#xff1a; 在这里插入图片描述 1.确定需求&#xff1a;在开始使用前&#xff0c;需要明确冬测的具体需求&#xff0c;例如需要记录的CAN总线数据类型、采样率、存储容量等。 2.连接硬件&#xff1a;将小巧的CAN总线记录仪与需要进行…

年终总结——平凡又不平凡的2023

前言 总结不知道该如何写起&#xff0c;也不知该如何建立这一篇文章的大致框架&#xff0c;只知道我的2023大概也就分成两大块罢了。说起2023一整年&#xff0c;只能用平凡而又不平凡来形容&#xff0c;平凡在我依旧没有什么太突出的技术点&#xff0c;专业水平也一直处于龟速…

无痛迁移:图解 Kubernetes 集群升级步骤

本文探究了Kubeadm集群升级工作流程&#xff0c;并以可视化方式展现。着重介绍了控制平面节点和工作节点的升级步骤&#xff0c;涵盖了kubeadm升级、节点清空、kubelet和kubectl升级&#xff0c;以及解除节点封锁的关键步骤。 这个简明扼要的指南可帮助用户理解和执行Kubernete…

计算机Java项目|基于Springboot实现患者管理系统

作者主页&#xff1a;编程指南针 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、掘金特邀作者、多年架构师设计经验、腾讯课堂常驻讲师 主要内容&#xff1a;Java项目、毕业设计、简历模板、学习资料、面试题库、技术互助 文末获取源码 项目编号&#xff1a;KS-032…

new FormData 同时发送表单 json 以及文件二进制流

需要新增时同时发送表单 json 以及对应的文件即可使用以下方法传参 let formDataParams new FormData(); 首先通过 new FormData&#xff08;&#xff09; 创建你需要最后发送的表单 接着将你的对象 json 存储&#xff0c;注意使用 new Blob 创建大表单转换成 json 格式。以…

交换机04_远程连接

通过远程管理方式连接交换机 1、telnet简介 telnet 是应用层协议 基于传输层TCP协议的&#xff0c;默认端口&#xff1a;23 采用的是明文密码方式 不是很安全&#xff0c;一般用于内网管理。 2、ssh协议简介 ssh 是应用层的协议&#xff0c;基于传输层的TCP协议&#x…

新手小白必了解c语言之字符串函数

本篇介绍字符串库函数为 目录 引言 一&#xff1a;字符串函数的头文件为#include 二&#xff1a;求字符串长度函数 &#xff08;strlen&#xff09; 1.函数介绍 2.函数使用举例 3.模拟实现 三&#xff1a;字符串复制函数(strcpy) 1.函数介绍 2.函数使用举例 3.模…

lombok注解 @Data使用在继承类上时出现警告解决

一、警告问题 1、Data注解 Data 包含了 ToString、EqualsAndHashCode、Getter / Setter和RequiredArgsConstructor的功能。 当使用 Data注解时&#xff0c;则有了 EqualsAndHashCode注解&#xff08;即EqualsAndHashCode(callSuperfalse)&#xff09;&#xff0c;那么就会在此…

uni-app 经验分享,从入门到离职(实战篇)——模拟从后台获取图片路径数据后授权相册以及保存图片到本地(手机相册)

文章目录 &#x1f4cb;前言⏬关于专栏 &#x1f3af;需求描述&#x1f3af;前置知识点&#x1f9e9;uni.showLoading()&#x1f9e9;uni.authorize()&#x1f9e9;uni.downloadFile()&#x1f9e9;uni.saveImageToPhotosAlbum() &#x1f3af;演示代码&#x1f9e9;关于图片接…

YOLOv5改进 | 2023 | SCConv空间和通道重构卷积(精细化检测,又轻量又提点)

一、本文介绍 本文给大家带来的改进内容是SCConv,即空间和通道重构卷积,是一种发布于2023.9月份的一个新的改进机制。它的核心创新在于能够同时处理图像的空间(形状、结构)和通道(色彩、深度)信息,这样的处理方式使得SCConv在分析图像时更加精细和高效。这种技术不仅适…