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文件…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
