二叉树(一)高度与深度
高度:从最底层往上数(后序遍历,左右根),更简单(递归)
深度:从上往下数直到有叶子(前序遍历,根左右),较复杂
高度是最大深度
一、求最大深度
int maxDepth(TreeNode* root) {//递归的终止条件if(root==NULL)return 0;//单层递归逻辑int leftheight=maxDepth(root->left); //左子树高度int rightHeight=maxDepth(root->right); //右子树高度int height=1+max(leftheight,rightHeight); //该树高度return height;}
二、求最小深度
int minDepth(TreeNode* root) {//递归的终止条件if(root==NULL)return 0;//单层递归逻辑int leftHeight=minDepth(root->left); //左子树的最小深度int rightHeight=minDepth(root->right); //右子树的最小深度if(!root->left&&root->right)//若左子树为空,最小深度是右子树深度+1return 1+rightHeight;if(root->left&&!root->right)//若右子树为空,最小深度是左子树深度+1return 1+leftHeight;return 1+min(leftHeight,rightHeight);//左右子树都有,选择最小深度+1}
三、判断是否为平衡二叉树
平衡二叉树:对每个结点来说,左右子树的高度差<=1
int getHeight(TreeNode* root){//递归终止条件if(root==NULL)return 0;//单层递归逻辑int leftHeight=getHeight(root->left);//左子树高度if(leftHeight==-1)return -1; int rightHeight=getHeight(root->right);//右子树高度if(rightHeight==-1)return -1;//如果做右子树高度差大于1,则返回-1(一直直接向上返回-1),否则就继续算高度int result=abs(leftHeight-rightHeight)>1?-1:1+max(leftHeight,rightHeight);return result;}bool isBalanced(TreeNode* root) {if(getHeight(root)==-1)return 0;return 1;}
四、总结
求高度或深度的题目,如果用递归来做,就是用栈(现进后出的思想),先自上而下“压入”进入递归,然后自下而上依次返回“蹦出”。
1、终止条件:
if(root==NULL)
return 0;
如果是空节点,说明是相对最底层(叶子之下),高度为0,从这里开始return,逐层返回加1
2、单层递归逻辑:
就是按照左右根的顺序,先求出左子树高度,然后求出右子树高度,再求根树的高度或最小深度或判断其他。
(1)求根树高度:返回1+max(leftHeight, rightHeight)
(2)求最小深度:返回1+min(leftHeight, rightHeight)
注意要先判断左右子树是否为空的情况!
(3)判断是否平衡:
比较左右子树的高度差
不平衡时,一直返回-1(很妙)
平衡时继续返回根树的高度
相关文章:
二叉树(一)高度与深度
高度:从最底层往上数(后序遍历,左右根),更简单(递归) 深度:从上往下数直到有叶子(前序遍历,根左右),较复杂 高度是最大深度 一、求…...
梧桐数据库(WuTongDB):MySQL 优化器简介
MySQL 优化器是数据库管理系统中的一个重要组件,用于生成并选择最优的查询执行计划,以提高 SQL 查询的执行效率。它采用了基于代价的优化方法(Cost-Based Optimizer, CBO),通过评估不同查询执行方案的代价,…...
交通运输部力推高速公路监测,做好结构安全预警,保护人民安全
在快速发展的交通网络中,高速公路作为经济命脉与生命通道,其结构安全直接关系到每一位行路者的生命财产安全。为此,广东省交通运输厅正式发布《关于积极申报高速公路监测预警应用示范揭榜的通知》,旨在通过技术创新与应用示范&…...
基于PHP+MySQL组合开发的在线客服源码系统 聊天记录实时保存 带完整的安装代码包以及搭建部署教程
系统概述 随着互联网技术的飞速发展,企业与客户之间的沟通方式日益多样化,在线客服系统作为连接企业与客户的桥梁,其重要性不言而喻。然而,市场上现有的在线客服系统往往存在成本高、定制性差、维护复杂等问题。针对这些痛点&…...
NEXT.js 创建postgres数据库-关联github项目-连接数据库-在项目初始化数据库的数据
github创建项目仓库创建Vercel账号选择hobby连接github仓库install - deploy创建postgres数据库(等待deploy完成) Continue to DashboardStorage(头部nav哪里)create Postgresconnect连接完后,切换到.env.local&#x…...
Matlab如何配置小波工具(Wavelet Toolbox)
1、发现问题 因为实验要使用小波工具函数,运行时报错如下: 查看对应文件夹发现没有小波工具(也可在控制台输入ver),检查是否有该工具,输入后回车返回如下: 2、下载工具包 没有这个工具就要去下…...
FTP、SFTP安装,整合Springboot教程
文章目录 前言一、FTP、SFTP是什么?1.FTP2.SFTP 二、安装FTP1.安装vsftp服务2.启动服务并设置开机自启动3.开放防火墙和SELinux4.创建用户和FTP目录4.修改vsftpd.conf文件5.启动FTP服务6.问题 二、安装SFTP1、 创建用户2、配置ssh和权限3、建立目录并赋予权限4、启动…...
24年蓝桥杯及攻防世界赛题-MISC-3
21 reverseMe 复制图片,在线ocr识别,https://ocr.wdku.net/,都不费眼睛。 22 misc_pic_again ┌──(holyeyes㉿kali2023)-[~/Misc/tool-misc/zsteg] └─$ zsteg misc_pic_again.png imagedata … text: “$$KaTeX parse error: Undefined…...
阿里云容器服务Kubernetes部署新服务
这里部署的是前端项目 1.登录控制台-选择集群 2.选择无状态-命名空间-使用镜像创建 3.填写相关信息 应用基本信息: 容器配置: 高级配置: 创建成功后就可以通过30006端口访问项目了...
记录生产环境,通过域名访问的图片展示不全,通过ip+端口的方式访问图片是完整的
原因:部署nginx的服务器硬盘满了 排查发现nginx日志文件占用了大量硬盘 解决方案: 删除该文件,重启nginx服务,问题解决。...
网络安全实训八(y0usef靶机渗透实例)
1 信息收集 1.1 扫描靶机IP 1.2 收集靶机的端口开放情况 1.3 探测靶机网站的目录 1.4 发现可疑网站 1.5 打开可疑网站 2 渗透 2.1 使用BP获取请求 2.2 使用工具403bypasser.py探测可疑网页 2.3 显示可以添加头信息X-Forwarded-For:localhost来访问 2.4 添加之后转发ÿ…...
QT信号槽原理是什么,如何去使用它?
QT的信号槽(Signals and Slots)机制是QT框架的核心特性之一,它提供了一种对象间通信的方式,使得QT的部件可以在不知道彼此详细实现的情况下相互通信。这种机制在图形用户界面编程中尤为重要,因为它有助于降低对象间的耦…...
mybatisplus介绍以及使用(上)
目录 一、概念 1、什么是mybatisplus 2、为什么要使用mybatisplus 二、mybatisplus的使用 1、安装 2、常用注解 3、条件构造器 一、概念 1、什么是mybatisplus MyBatis-Plus(简称MP)是一个基于MyBatis的增强框架,旨在简化开发、提高…...
maxwell 输出消息到 redis
文章目录 1、maxwell 输出消息到 redis1.1、启动一个Maxwell容器,它会连接到指定的MySQL数据库,捕获变更事件,并将这些事件以Redis发布/订阅的形式发送到指定的Redis服务器1.2、在已运行的 Redis 容器中执行 Redis 命令行界面(CLI…...
infoNCE损失和互信息的关系
文章目录 InfoNCE 损失与互信息的关系推导将相似度 sim ( q , x ) \text{sim}(q, x) sim(q,x) 看作是负的能量函数infoNCE和互信息的分母不同 InfoNCE 损失与互信息的关系推导 为了理解 InfoNCE 损失与互信息的关系,首先我们回顾两个公式的基本形式: 互…...
Java学习路线指南
目录 前言1. Java基础知识1.1 面向对象编程思想1.2 Java平台与JVM1.3 Java语言的核心概念 2. Java语法与基础实践2.1 数据类型与变量2.2 控制结构2.3 方法与函数2.4 数据结构与集合框架 3. Java进阶知识3.1 异步编程与多线程3.2 JVM调优与垃圾回收机制3.3 设计模式 4. 实践与项…...
在SpringCloud中实现服务间链路追踪
在微服务架构中,由于系统的复杂性和多样性,往往会涉及到多个服务之间的调用。当一个请求经过多个服务时,如果出现问题,我们希望能够快速定位问题所在。这就需要引入链路追踪机制,帮助我们定位问题。 Spring Cloud为我们…...
[数据集][目标检测]红外微小目标无人机直升机飞机飞鸟检测数据集VOC+YOLO格式7559张4类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):7559 标注数量(xml文件个数):7559 标注数量(txt文件个数):7559 标注…...
TS Vue项目中使用TypeScript
模块系统与命名空间 概念 模块化开发是目前最流行的组织代码方式,可以有效的解决代码之间的冲突与代码之间的依赖关系,模块系统一般视为“外部模块”,而命名空间一般视为“内部模块” 模块系统 TS中的模块化开发跟ES6中的模块化开发并没有…...
打工人、设计师必备的AI抠图工具
前言 你是否厌倦了繁琐的PS操作?是否在寻找一种快速、简便的抠图方法?别担心,AI技术已经为你准备好了解决方案。以下是9个令人惊叹的AI抠图工具,让你无需PS也能轻松获得专业级别的抠图效果。 1. 千鹿设计助手:EmGaur…...
libmill内存管理机制:如何避免协程栈溢出问题的完整指南
libmill内存管理机制:如何避免协程栈溢出问题的完整指南 【免费下载链接】libmill Go-style concurrency in C 项目地址: https://gitcode.com/gh_mirrors/li/libmill libmill是一个为C语言引入Go风格并发编程的轻量级库,它通过协程(c…...
图像修复效率提升:设计师与开发者必备的7个开源AI模型应用技巧
图像修复效率提升:设计师与开发者必备的7个开源AI模型应用技巧 【免费下载链接】ComfyUI-BrushNet ComfyUI BrushNet nodes 项目地址: https://gitcode.com/gh_mirrors/co/ComfyUI-BrushNet 在数字创作与内容修复领域,如何快速高效地消除图像瑕疵…...
WPF Chart控件实战:构建高性能实时数据监控曲线
1. WPF Chart控件基础入门 第一次接触WPF Chart控件时,我也被它强大的功能震撼到了。这个控件就像是一个神奇的画板,能够将枯燥的数据变成直观的曲线图。在工业监控系统中,我们经常需要实时显示温度、压力等参数的变化趋势,这时候…...
Magisk系统权限架构深度解析:Android设备Root权限优雅解决方案
Magisk系统权限架构深度解析:Android设备Root权限优雅解决方案 【免费下载链接】Magisk The Magic Mask for Android 项目地址: https://gitcode.com/GitHub_Trending/ma/Magisk Magisk作为Android系统权限管理领域的革命性工具,通过独特的系统化…...
RSA1 - Writeup by AI
RSA1 - Writeup by AI 1. 题目描述项目内容题目来源Bugku题目类型Crypto (密码学)考点RSA 大数分解、私钥计算题目信息 题目给出了 RSA 加密的三个参数: e 65537 N 1018261336751023520497560395829454421245429586704872293236600679847605951423419167478189648…...
告别音乐平台干扰!铜钟音乐如何让你重拾纯净听歌体验?
告别音乐平台干扰!铜钟音乐如何让你重拾纯净听歌体验? 【免费下载链接】tonzhon-music 铜钟 (Tonzhon.com): 免费听歌; 没有直播, 社交, 广告, 干扰; 简洁纯粹, 资源丰富, 体验独特!(密码重置功能已回归) 项目地址: https://gitcode.com/Gi…...
FRCRN开源模型部署指南:国产昇腾Ascend 910B适配与性能实测
FRCRN开源模型部署指南:国产昇腾Ascend 910B适配与性能实测 1. 项目概述与背景 FRCRN(Frequency-Recurrent Convolutional Recurrent Network)是阿里巴巴达摩院在ModelScope社区开源的单通道语音降噪模型,专门针对16kHz采样率的…...
OWL ADVENTURE编辑功能展示:一键换装、智能擦除,效果自然
OWL ADVENTURE编辑功能展示:一键换装、智能擦除,效果自然 1. 编辑功能概览:像玩游戏一样修图 OWL ADVENTURE的图片编辑功能让人眼前一亮。不同于传统修图软件的复杂操作,它通过自然语言指令就能完成各种编辑任务,效果…...
如何高效管理微信读书笔记:终极免费工具wereader完全指南
如何高效管理微信读书笔记:终极免费工具wereader完全指南 【免费下载链接】wereader 一个功能全面的微信读书笔记助手 wereader 项目地址: https://gitcode.com/gh_mirrors/we/wereader 微信读书助手wereader是一款专为微信读书用户设计的免费开源工具&#…...
PingFangSC跨平台字体解决方案:企业级部署与性能优化指南
PingFangSC跨平台字体解决方案:企业级部署与性能优化指南 【免费下载链接】PingFangSC PingFangSC字体包文件、苹果平方字体文件,包含ttf和woff2格式 项目地址: https://gitcode.com/gh_mirrors/pi/PingFangSC 在数字化转型浪潮中,企业…...
