剑指 Offer 55 - I. 二叉树的深度

news/2024/3/29 18:28:40/文章来源:https://blog.csdn.net/weixin_41605937/article/details/129184464

摘要

剑指 Offer 55 - I. 二叉树的深度

一、深度优先搜索

如果我们知道了左子树和右子树的最大深度l和r,那么该二叉树的最大深度即为:max(l,r)+1。

而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言,在计算当前二叉树的最大深度时,可以先递归计算出其左子树和右子树的最大深度,然后在 O(1)O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}
}

复杂度分析

  • 时间复杂度:O(n)O(n),其中 nn 为二叉树节点的个数。每个节点在递归中只被遍历一次。
  • 空间复杂度:O(height)O(height),其中 heightheight 表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度。

二、广度优先搜索

我们也可以用广度优先搜索的方法来解决这道题目,但我们需要对其进行一些修改,此时我们广度优先搜索的队列里存放的是当前层的所有节点。每次拓展下一层的时候,不同于广度优先搜索的每次只从队列里拿出一个节点,我们需要将队列里的所有节点都拿出来进行拓展,这样能保证每次拓展完的时候队列里存放的是当前层的所有节点,即我们是一层一层地进行拓展,最后我们用一个变量 ans来维护拓展的次数,该二叉树的最大深度即为 ans。

    public int maxDepth2(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<TreeNode>();// 加入root节点queue.offer(root);int ans = 0;while (!queue.isEmpty()) {int size = queue.size();while (size > 0) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}size--;}// 将每一层的队列的值都弹出即为深度数ans++;}return ans;}

复杂度分析

  • 时间复杂度:O(n),其中n为二叉树的节点个数。与方法一同样的分析,每个节点只会被访问一次。
  • 空间复杂度:此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到O(n)。

三、平衡二叉树

判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

有了计算节点高度的函数,即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历,即对于当前遍历到的节点,首先计算左右子树的高度,如果左右子树的高度差是否不超过1,再分别递归地遍历左右子节点,并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

package Tree;/*** @Classname JZ55平衡二叉树* @Description TODO* @Date 2023/2/23 16:51* @Created by xjl*/
public class JZ55平衡二叉树 {public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}public boolean isBalanced(TreeNode root) {if (root == null) {return true;} else {// 要求这个左子树的和右子树都要小于这个,同时要求这个树本身的高度差不能超过1return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);}}public int height(TreeNode root) {if (root == null) {return 0;} else {// 返回的是这个树的高度return Math.max(height(root.left), height(root.right)) + 1;}}
}

复杂度分析

  • 时间复杂度:O(n^2),其中n是二叉树中的节点个数。最坏情况下,二叉树是满二叉树,需要遍历二叉树中的所有节点,时间复杂度是 O(n)。对于节点p,如果它的高度是d,则height(p)最多会被调用d次(即遍历到它的每一个祖先节点时)。对于平均的情况,一棵树的高度h 满足O(h)=O(log⁡n),因为 d≤h,所以总时间复杂度为 O(nlog⁡n)。对于最坏的情况,二叉树形成链式结构,高度为 O(n),此时总时间复杂度为 O(n^2)
  • 空间复杂度:O(n),其中 n是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数,递归调用的层数不会超过n。

博文参考

《leetcode》

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

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

相关文章

校园学生翻墙打架识别检测系统 yolov7

校园学生翻墙打架识别检测系统通过yolov7网络模型深度学习分析技术&#xff0c;校园学生翻墙打架识别检测算法可以对&#xff1a;打架行为、倒地行为识别、人员拥挤行为、攀高翻墙违规行为等违规行为进行实时分析检测。YOLOv7 的发展方向与当前主流的实时目标检测器不同&#x…

动手学深度学习v2—01数据操作+数据预处理

[TOC]此次用到的虚拟环境&#xff1a;pytorchmwy项目名称&#xff1a;limuAI所需框架和工具&#xff1a;pytorch&#xff0c;pandas一、创建CSV文件所需工具&#xff1a;pandas在与项目同等目录下创建一个文件夹名为data&#xff0c;其中文件名称为house_tiny.csv。代码如下&am…

随想录二刷 (双指针法) leetcode 27 26 283 844

双指针法的原理 双指针法相对于暴力解法的优点有以下几点 暴力遍历的时间复杂度会比较高双指针法利用两个指针进行遍历完成双层循环所做的事情 双指针一般有两种方法 同向指针&#xff0c;双向指针 第一题 leetcode 27 移除元素 题目描述 题目分析 采用暴力遍历可以得出结…

高效制作知识库的软件工具,这6个都很不错哦!

任何工作流程都离不开文档管理&#xff0c;因此文档管理也是企业数字化转型中的重要环节。面对复杂的业务流程、频繁的文档编辑任务和跨区域的文件共享需求&#xff0c;优秀的文档管理体系能够帮助企业实现安全的文档存储&#xff0c;高效的文档搜索&#xff0c;便捷的文档协作…

(一)Spring-Cloud源码分析之核心流程关系及springcloud与springboot包区别(新)

文章目录1. 前言2. springcloud简介3. Springcloud包简介4. Springcloud和Springboot流程关系5. Springcloud启动流程新增的功能和接口5.1 新增接口5.2 新增功能类5.2.1 spring-cloud-context包5.2.2 spring-cloud-commons包6. Springcloud实现机制带来的问题7. Springcloud和S…

深入浅出C++ ——手撕红黑树

文章目录一、红黑树的概念二、红黑树的性质三、红黑树节点的定义四、红黑树的插入操作五、红黑树的验证五、红黑树的删除六、红黑树与AVL树的比较七、红黑树的应用八、红黑树模拟实现一、红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存…

Typecho COS插件实现网站静态资源存储到COS,降低本地存储负载

Typecho 简介Typecho 是一个简单、强大的轻量级开源博客平台&#xff0c;用于建立个人独立博客。它具有高效的性能&#xff0c;支持多种文件格式&#xff0c;并具有对设备的响应式适配功能。Typecho 相对于其他 CMS 还有一些特殊优势&#xff1a;包括可扩展性、不同数据库之间的…

(二十五)、实现评论功能(5)【uniapp+uinicloud多用户社区博客实战项目(完整开发文档-从零到完整项目)】

1&#xff0c;实现二级回复的入库操作 1.1 两个子组件&#xff08;comment-item和comment-frame&#xff09;与父组件reply之间的属性传值 comment-item&#xff1a; props: {item: {type: Object,default () {return {}}}},comment-frame&#xff1a; props: {commentObj: {…

儿童饰品发夹发卡出口美国办理什么认证?

亚马逊美国站上传新产品&#xff0c;很多时候都是需要类目审核的&#xff0c;后台给出要求提供认证&#xff0c;产品类目不同&#xff0c;所需要提供的认证证书是不一样&#xff0c;儿童产品需要提交的是CPC认证&#xff0c;玩具&#xff0c;母婴用品&#xff0c;儿童书包&…

PDF文件怎么转图片格式?转换有技巧

PDF文件有时为了更美观或者更直观的展现出效果&#xff0c;我们会把它转成图片格式&#xff0c;这样不论是归档总结还是存储起来都会更为高效。有没有合适的转换方法呢&#xff1f;这就来给你们罗列几种我个人用过体验还算不错的方式&#xff0c;大家可以拿来参考一下哈。1.用电…

Apifox = Postman + Swagger + Mock + JMeter

目录 可视化API设计 高效 & 零学习成本 可复用的“数据模型” 遵循 OpenAPI(Swagger) 规范 可导入 Swagger 等 20 数据格式 具体使用尝鲜 多项目管理 支持多环境切换 支持IDEA、浏览器、桌面应用 Idea插件 公共API hub库 如题&#xff1a;一款非常好用的API管理测…

Wi-Fi 7技术揭秘

引言 2022年4月7日&#xff0c;紫光股份旗下新华三集团全球首发企业级智原生Wi-Fi 7 AP新品 WA7638和WA7338。仅在同年的6月15日&#xff0c;在东京举行的第29届日本网络通信展览会&#xff08;Interop Tokyo 2022&#xff0c;简称Interop展&#xff09;中&#xff0c;WA7638就…

D1s RDC2022纪念版开发板开箱评测及点屏教程

作者new_bee 本文转自&#xff1a;https://bbs.aw-ol.com/topic/3005/ 目录 芯片介绍开发板介绍RT-Smart用户态系统编译使用感想引用 1. 芯片介绍 RISC-V架构由于其精简和开源的特性&#xff0c;得到业界的认可&#xff0c;近几年可谓相当热门。操作系统方面有RT-Thread&am…

Firebase常用功能和官方Demo简介

一、Firebase简介Firebase刚开始是一家实时后端数据库创业公司&#xff0c;它能帮助开发者很快的写出Web端和移动端的应用。自2014年10月Google收购Firebase以来&#xff0c;用户可以在更方便地使用Firebase的同时&#xff0c;结合Google的云服务。现在的Firebase算是谷歌旗下的…

模拟信号4-20mA /0-5V/0-75mV/0-100mV转RS-485/232,数据采集A/D转换模块 YL21

特点&#xff1a;● 模拟信号采集&#xff0c;隔离转换 RS-485/232输出● 采用12位AD转换器&#xff0c;测量精度优于0.1%● 通过RS-485/232接口可以程控校准模块精度● 信号输入 / 输出之间隔离耐压3000VDC ● 宽电源供电范围&#xff1a;8 ~ 32VDC● 可靠性高&#xff0c;编程…

界面控件DevExpress WinForm——轻松构建类Visual Studio UI(二)

DevExpress WinForm拥有180组件和UI库&#xff0c;能为Windows Forms平台创建具有影响力的业务解决方案。DevExpress WinForm能完美构建流畅、美观且易于使用的应用程序&#xff0c;无论是Office风格的界面&#xff0c;还是分析处理大批量的业务数据&#xff0c;它都能轻松胜任…

海思SD3403/SS928V100开发(5)MIPI_YUV相机vio sample开发----修改思路

1. 前言 sensor输出格式: YUV422 8bit 硬件连接: MIPI_YUV相机(4lane MIPI) -> SS928V100 MIPI0(4lane) 框图: 2. 几个问题 基于SS928 SDK中的 vio sample修改; 但是sample里面都是基于RAW RGB sensor开发的sample, 没有现成的MIPI_YUV sensor的参考,需要自己…

CentOS 8利用Apache安装部署下载服务器

1&#xff1a;部署的目的是做一个类似下面开源镜像网站&#xff0c;把一些软件或者资料上传到服务器上面&#xff0c;减少用户在互联网上下载资料&#xff0c;提高效率&#xff0c;减少病毒。 2&#xff1a;使用下面的命令配置本机的IP地址主机名等信息。后期使用IP地址进行访问…

11技术太卷我学APEX-数据加载

11技术太卷我学APEX-数据加载 0 所谓的数据加载 就是导入数据到数据库表中&#xff0c;本示例就采用Excel导入数据到《技术太卷我学APEX》的apex_learn表。表结构大概是这样的 CREATE TABLE "APEX_LEARN" ( "P_ID" NUMBER(17,0) NOT NULL ENABLE, &quo…

【Elasticsearch】安装配置与使用

一、下载与安装Elasticsearch下载地址&#xff1a;https://www.elastic.co/cn/downloads/elasticsearch#ga-release前端管理界面&#xff1a;https://github.com/mobz/elasticsearch-head这两个文件都是解压即可。二、配置与启动1.elasticsearch6以上的版本已经内置jdk&#xf…