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文件…...
OpenClaw:AI 权限治理的核心问题
子玥酱 (掘金 / 知乎 / CSDN / 简书 同名) 大家好,我是 子玥酱,一名长期深耕在一线的前端程序媛 👩💻。曾就职于多家知名互联网大厂,目前在某国企负责前端软件研发相关工作,主要聚…...
东北老牌央国企陪跑机构哪家实力强
在东北地区,众多求职者,特别是应届毕业生,将目光投向了工作稳定、发展前景广阔的央国企。在这一背景下,专业的求职服务机构应运而生,为求职者提供系统化的支持。辽宁优泰教育咨询有限公司便是其中一家专注于该领域的服…...
AI教材生成强力工具!低查重保障,让教材编写事半功倍!
梳理教材知识点确实是一项“精细活”,最大的挑战在于平衡和衔接知识之间的关系。如果不小心,很可能会遗漏一些核心知识点,或者在难度的把控上出现问题——小学教材常常写得过于复杂,让学生难以理解;而高中教材又可能显…...
OpenClaw浏览器自动化:ollama-QwQ-32B驱动的研究资料收集系统
OpenClaw浏览器自动化:ollama-QwQ-32B驱动的研究资料收集系统 1. 为什么需要自动化研究资料收集 作为一名经常需要查阅大量文献的技术写作者,我长期被资料收集的效率问题困扰。传统工作流程中,我需要手动在Google Scholar、arXiv、知乎等平…...
OpenClaw硬件选购指南:百川2-13B-4bits量化版在不同GPU上的表现
OpenClaw硬件选购指南:百川2-13B-4bits量化版在不同GPU上的表现 1. 为什么需要关注硬件配置 去年冬天,当我第一次尝试在本地部署OpenClaw对接百川2-13B模型时,我的旧显卡GTX 1660 Ti直接崩溃了。那次经历让我深刻认识到——选择合适的硬件对…...
零基础一键配置黑苹果:OpCore-Simplify智能工具让复杂变简单
零基础一键配置黑苹果:OpCore-Simplify智能工具让复杂变简单 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 还在为黑苹果配置时面对满屏代…...
基于Python的本科生交流培养管理平台毕业设计源码
博主介绍:✌ 专注于Java,python,✌关注✌私信我✌具体的问题,我会尽力帮助你。 一、研究目的 本研究旨在设计并实现一个基于Python的本科生交流培养管理平台,以提升我国高等教育中本科生交流培养的质量与效率。具体研究目的如下:…...
ABC系统实战指南:逻辑综合与形式验证的数字电路设计工具
ABC系统实战指南:逻辑综合与形式验证的数字电路设计工具 【免费下载链接】abc ABC: System for Sequential Logic Synthesis and Formal Verification 项目地址: https://gitcode.com/gh_mirrors/ab/abc 在现代数字电路设计流程中,逻辑综合与形式…...
微信小程序--动态切换登录注册标签页
1、try.js的 1.1、data函数 添加 activeTab: login, // 当前激活的标签,默认为登录 1.2、添加一个函数 // 切换登录/注册标签switchTab(e) {const tab e.currentTarget.dataset.tab;this.setData({activeTab: tab});}, 2、try.wxml的代码 <!--pages/try/…...
不止于公式:用国民技术N32G45x定时器实现精准时间片调度(附代码)
不止于公式:用国民技术N32G45x定时器实现精准时间片调度(附代码) 在嵌入式系统开发中,定时器是最基础也最强大的外设之一。对于国民技术N32G45x系列微控制器而言,其丰富的定时器资源(TIM2/3/4等)…...
