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文件…...
nli-distilroberta-base代码实例:Python调用DistilRoBERTa实现Entailment识别
nli-distilroberta-base代码实例:Python调用DistilRoBERTa实现Entailment识别 1. 项目概述 自然语言推理(Natural Language Inference, NLI)是自然语言处理中的一项重要任务,用于判断两个句子之间的逻辑关系。nli-distilroberta-base是基于DistilRoBER…...
Vue3项目救星:我是如何用Cursor的‘项目规则’功能,让团队新人一天上手的
Vue3团队协作革命:用Cursor项目规则实现代码规范的自动化治理 当新成员加入你的Vue3项目时,是否经历过这样的场景?新人提交的代码里混杂着选项式API和组合式API,路由命名忽而短横线忽而大驼峰,样式文件里散落着各种魔…...
IPD实战指南:CBB模块化设计如何加速产品创新与资源整合
1. CBB模块化设计的本质与价值 第一次接触CBB这个概念时,我正负责一款智能家居产品的研发。当时团队为了赶进度,每个新产品都从零开始设计电路板,结果发现80%的功能模块都是重复的。这种低效的开发方式让我开始思考:能不能像搭积木…...
MarkDownload:让网页转Markdown变得简单高效的浏览器扩展
MarkDownload:让网页转Markdown变得简单高效的浏览器扩展 【免费下载链接】markdownload A Firefox and Google Chrome extension to clip websites and download them into a readable markdown file. 项目地址: https://gitcode.com/gh_mirrors/ma/markdownload…...
GPT-5.4 Pro接入Java!百万上下文+电脑操控,Spring AI集成教程
文章目录前言一、先搞清楚你在驯服什么野兽二、Spring AI Alibaba是什么鬼?核心优势三、环境准备:别在JDK版本上栽跟头四、基础对话:先让AI开口说话五、百万上下文的正确打开方式六、Computer Use:让AI真的动起来实际应用场景七、…...
【算法对抗】打穿查重黑盒!论文降AI太难?8个实测有效策略与高性价比工具
上周匆匆写完论文初稿交给导师,结果被一眼识破,当场打回。还被导师认为不认真不负责态度不端正! 为了搞定这件事,我测评了市面上大部分的主流工具、试了无数方法,终于把AI率降到6%。 我们要先端正态度:论文…...
46535
4675328...
【AI重塑科研】无需通读全文,三步教你用大模型高效产出文献综述
1. 为什么你需要AI辅助文献综述? 每次打开文献库看到上百篇待读论文就头皮发麻?我完全理解这种感受。去年准备开题报告时,导师要求我两周内完成50篇核心文献的综述,当时差点崩溃。直到我发现用大模型处理文献可以节省90%的时间&am…...
Wan2.2-I2V-A14B部署教程:系统盘50GB+数据盘40GB最小化配置实操
Wan2.2-I2V-A14B部署教程:系统盘50GB数据盘40GB最小化配置实操 1. 镜像概述与核心特性 Wan2.2-I2V-A14B是一款专为文生视频任务优化的私有部署镜像,特别针对RTX 4090D 24GB显存显卡进行了深度优化。这个镜像最大的特点是开箱即用,内置了完整…...
智能突破2048:AI助手如何让数字合成不再依赖运气
智能突破2048:AI助手如何让数字合成不再依赖运气 【免费下载链接】2048-ai AI for the 2048 game 项目地址: https://gitcode.com/gh_mirrors/20/2048-ai 你是否曾在2048游戏中陷入数字迷宫?眼看着屏幕上散落的方块无从下手,移动一步就…...
