day19-二叉树的最大最小深度
二叉树的最大/最小深度
给定一个二叉树 root ,返回其最大/小深度。
二叉树的 最大/小深度 是指从根节点到最远/近叶子节点的最长路径上的节点数。
思路
求最大深度比较简单,我们先解决最大深度。
最大深度
递归
class Solution {
public:int maxDepth(TreeNode* root) {if(root == null)return 0;return max(maxDepth(root->left),maxDepth(root->right))+1;}
};
非常简单的一句代码。但是理解起来却有点难度。
终止条件为:root == null时返回0。
想一想,当结点为空时,此时高度是不存在的,因此返回0。
而递归的逻辑是:我们需要在根节点的左子树和右子树中选最大值,所以这里用max(x,y)返回。
当递归到空节点开始返回,一开始返回0,后面逐渐+1…,到根节点就得到这颗子树的高度。
层序遍历
class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*> qu;if(root != nullptr)qu.push(root);else return 0;int ans = 0;while(!qu.empty()){int size = qu.size();for(int i=0;i<size;i++){TreeNode* node = qu.front();qu.pop();if(node->left != nullptr)qu.push(node->left);if(node->right != nullptr)qu.push(node->right);}ans++;}return ans;}
};
这里用的是层序遍历,也即是广度优先,对每一层的结点进行遍历,然后同时ans++;
其实最大深度就是求的最大高度,因此有多少层可以遍历即高度多少。
最小深度
递归
- 当root为空,则当前高度为0
- 当root的左右子节点均为空,则当前为叶子结点,高度为1
- 如果左右子节点有一个为空,则m_left和m_right必有一个为0,则直接返回两者相加+1
- 最后一种情况则是左右子节点均不为空,则返回左右子树深度小的
class Solution {
public:int minDepth(TreeNode* root) {if(root == nullptr)return 0;if(root->left== nullptr && root->right ==nullptr)return 1;int m_left = minDepth(root->left);int m_right = minDepth(root->right);return root->left == nullptr || root->right ==nullptr ?m_left+m_right+1:min(m_right,m_left)+1;}
};
层序遍历
相比递归,BFS要简单的多,我们只需要找到第一个叶子节点,然后返回即可,找不到,没关系,继续遍历下一层。
class Solution {
public:int minDepth(TreeNode* root) {queue<TreeNode*> qu;if(root != nullptr)qu.push(root);else return 0;int ans = 1;while(!qu.empty()){int size = qu.size();for(int i=0;i<size;i++){TreeNode* cur = qu.front();qu.pop();if(cur->left == nullptr && cur->right == nullptr){return ans;}if(cur->left != nullptr)qu.push(cur->left);if(cur->right != nullptr)qu.push(cur->right);}ans++;}return ans;}
};
注意的是,ans一开始初始化为1,是因为根节点自身便带有高度,只有空结点会为0。
相关文章:
day19-二叉树的最大最小深度
二叉树的最大/最小深度 给定一个二叉树 root ,返回其最大/小深度。 二叉树的 最大/小深度 是指从根节点到最远/近叶子节点的最长路径上的节点数。 思路 求最大深度比较简单,我们先解决最大深度。 最大深度 递归 class Solution { public:int maxD…...
Ansible-roles
Ansible-roles 一、roles作用 把playbook剧本里的各个play看作为角色,将各个角色的tasks任务、vars变量、templates模板、files文件等内容放置到角色的目录中统一管理,需要的时候可在playbook中直接使用roles调用,所以roles可以实现playboo…...
NullPointerException导致手机重启案例分析
和你一起终身学习,这里是程序员Android 经典好文推荐,通过阅读本文,您将收获以下知识点: 一、 Framework 层对象 空指针导致手机重启。二、解决方案,规避空指针三、Telecom APK 控制导致的重启举例 一、 Framework 层对象 空指针导…...
JAVA 反编译工具
Releases deathmarine/Luyten GitHub 安装exe 打开拖入文件即可...
(AcWing)分组背包问题
有 N 组物品和一个容量是 V 的背包。 每组物品有若干个,同一组内的物品最多只能选一个。 每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。 求解将哪些物品装入背包,可使物品总体积不超过背包容量&…...
JSP项目国际化词条统计
国际化字条匹配并导出为excel格式 需求 将jsp页面里的key值,就是<spring:message code"gsyezer_Single_crystal"/>里的gsyezer_Single_crystal。和对应的字条对应上,并以excel表格形式输出。 jsp页面key值示例 <label for"&…...
Java课题笔记~ MyBatis缓存
为了减少重复查询给数据库带来的压力,MyBatis提供了缓存机制,这种机制能够缓存查询的结果,避免重复的查询。 MyBatis提供了两种缓存方式: 一种为针对于SqlSession的缓存【默认开启】 另一种为针对于全局的缓存【手动开启】 一…...
数据结构--循环队列、链队
基础知识 //循环队列数据结构 typedef struct { QElemType data[MaxQSize];//数据域 int front,rear; //队头队尾指针 }SqQueue; //链队结点数据结构 typedef struct QNode { int data;//数据域 struct QNode* next;//指针域 }QNode, * QueuePtr; typedef struct { struct Q…...
hbuilderx主题色分享-github风格
效果 步骤 hbuilderx总共有三种主题,绿柔主题Default,酷黑主题Monokai,雅黑主题Atom One Dark,修改主题色是基于三种主题之一的,不能直接创建一个新主题,比如下方配置是基于Atom One Dark(对象名为[Atom One Dark]),则当前hbuild…...
【C++】类与对象(1)
文章目录 前言一、什么是类1.类的定义2.类的访问限定符3.类的作用域 二、类的实例化三、类对象的存储方式四、this指针总结 前言 C语言是面向过程的,关注的是过程,分析出求解问题的步骤,通过函数调用逐步解决问题。C是基于面向对象的&#x…...
Java课题笔记~ MyBatis核心配置
一、核心配置文件概览 MyBatis配置文件中有MyBatis框架的核心配置,负责对MyBatis进行全局管理。它包含许多控制MyBatis功能的重要元素。 <configuration><!--设置配置文件--><properties><property name"" value""/>…...
从0开始自学网络安全(黑客)
前言 黑客技能是一项非常复杂和专业的技能,需要广泛的计算机知识和网络安全知识。你可以参考下面一些学习步骤,系统自学网络安全。 在学习之前,要给自己定一个目标或者思考一下要达到一个什么样的水平,是学完找工作(…...
kotlin 编写一个简单的天气预报app(四)增加界面显示
编写界面来显示返回的数据 用户友好性:通过界面设计和用户体验优化,可以使天气信息更易读、易理解和易操作。有效的界面设计可以提高用户满意度并提供更好的交互体验。 增加城市名字的TextView <TextViewandroid:id"id/textViewCityName"…...
英语不好能学好Python吗?Python常用英文单词汇总
前言 嗨喽,大家好呀~这里是爱看美女的茜茜呐 有些小可爱对英语好不好对学习python有没有什么影响有着很深的疑惑。 其实python学习,主要靠多敲多练,主打一个熟能生巧 那今天我就给大家带来Python常用英文单词汇总, 新手期小可…...
Counting Stars 2023“钉耙编程”中国大学生算法设计超级联赛(5)hdu7335
Problem - 7335 题目大意:如果一个点连接着k个点,就称这k1个点构成k星图,现给出一个大小为n的图,问2星图的数量^3星图的数量^...^n星图的数量是多少 3<n<1e6;1<m<1e6 思路:因为边数总共不超过1e6&#…...
浅谈document.write()输出样式
浅谈document.write()输出样式 js中的最基本的命令之一:document.write(),用于简单的打印内容到页面上,可以逐字打印你需要的内容——document.write("content"),这里content就是需要输出的内容;…...
AIGC(Artificial Intelligence and Graph Computing)职业发展路径和前景如何?
目录 一、AIGC 基本概念二、AIGC 市场规模三、AIGC 未来发展前景四、AIGC 职业发展路径五、AIGC 技能要求六、AIGC 相关公司 AIGC(Artificial Intelligence and Graph Computing)是人工智能和图计算的结合,它是一种用于处理大规模复杂数据的计…...
MySql006——基本的SELECT查询语句
在《MySql003——结构化查询语言SQL基础知识》中,我们学习了有关SQL的基础知识,也知道SQL中查询语句SELECT使用最为频繁 接下来我们将学习一些基本的SELECT查询语句 一、SELECT语句的通用语法 在MySQL数据库中,使用SELECT语句可以查询数据…...
【啥都生】分类项目中的模型搭建代码解析
def build_model(cfg):if isinstance(cfg, list):modules [eval(cfg_.pop("type"))(**cfg_) for cfg_ in cfg]return Sequential(*modules)else:return eval(cfg.pop("type"))(**cfg)b站up啥都生维护的分类项目 这段代码的功能是完成模型搭建,…...
Ubuntu出现了内部错误
使用的Ubuntu版本是18.04,使用的时候弹出对话框说出现了内部错误,好奇是哪里出现了错误,查找了一下解决的办法,记录一下。 参考解决方案:ubantu出现了内部错误 一旦程序崩溃过一次,就会生成一个.crash文件…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
