【代码随想录训练营】【Day21】第六章|二叉树|530.二叉搜索树的最小绝对差|501.二叉搜索树中的众数|236. 二叉树的最近公共祖先
二叉搜索树的最小绝对差
题目详细:LeetCode.530
这道题使我第一次了解到二叉树的双指针遍历法,详细可以先查看卡哥的讲解视频:《代码随想录 — 二叉搜索树中的众数》
利用二叉搜索树的特点:
- 中序遍历二叉搜索树得到一个有序序列
- 计算序列中相邻的每一个数的差值,记录最小绝对值差
但我们可以发现,如果我们可以在遍历过程中去计算相邻的两个数的差值,那么速度将提升很多,对于序列是否有序这一点似乎并不是特别重要,只是二叉搜索树赋予了它这一特点。
那么我们可以利用双指针法:
- 定义一个指针 pre 指向当前节点的前一个节点
- 按照左中右的顺序,深度优先遍历树的节点
- 若 pre 为空,则说明当前节点为叶子节点,不存在前一个节点
- 若 pre 不为空,则计算前一个节点与当前节点的绝对差值,利用全局变量记录一个最小值结果
- 注意更新前一个节点 pre = cur
Java解法(递归):
class Solution {public int ans = Integer.MAX_VALUE;public TreeNode pre = null;public int getMinimumDifference(TreeNode root) {this.dfs(root);return ans;}public void dfs(TreeNode cur){if(null == cur) return;this.dfs(cur.left);if(null != this.pre){ans = Math.min(ans, Math.abs(pre.val - cur.val));}this.pre = cur;this.dfs(cur.right);}
}
二叉搜索树中的众数
题目详细:LeetCode.501
传统的暴力解法有:
- 解法一:得到中序遍历序列后统计序列中出现次数最多的数字
- 解法二:遍历一次二叉树记录最高出现频率,再中序遍历一次二叉树将出现频率等于最高出现频率的数字加入结果集
- 这种方法都相当于需要遍历两次二叉树,效率较低,这里就不多赘述了
那么我们能否利用二叉搜索树中序遍历有序的特点,在遍历过程中就统计最高出现频率的数字呢?
在经过上一题了解二叉搜索树中双指针法的应用后,在遇到二叉搜索树相关问题时就又多了一种解题思路(中序遍历+双指针法):
- 定义两个变量,times 记录当前数字的出现频率,max_times 记录最高出现频率
- 众所周知,利用二叉搜索树的特点通过中序遍历可以得到一个有序序列
- 因为中序遍历结果是有序序列,所以数字一定是递增地连续地出现的,那么利用双指针法:
- 在递归中序遍历二叉树的过程中,通过比较 pre 和 cur 的数值,记录当前数字的出现频率
- 比较当前出现频率和最高出现频率
- 若当前出现频率等于最高出现频率,那么将数字加入结果集
- 若当前出现频率高于已知的最高出现频率,那么更新最高出现频率,并清空当前结果集后,再加入当前数字
Java解法(中序遍历+双指针法):
class Solution {public List<Integer> ans = new ArrayList<>();public int max_times = 1, times = 1;public TreeNode pre = null;public int[] findMode(TreeNode root) {this.dfs(root);return ans.stream().mapToInt(Integer::valueOf).toArray();}public void dfs(TreeNode cur){if(null == cur) return ;// 左this.dfs(cur.left);// 中// 记录当前数字的出现频率if(null != this.pre){if(cur.val == this.pre.val){this.times++;}else{this.times = 1;}}if(this.times == this.max_times){// 如果出现频率等于最高频率,那么将数字加入结果集this.ans.add(cur.val);}else if(this.times > this.max_times){// 如果出现频率高于已知的最高频率,那么更新最高频率,并清空当前结果集后再加入新的数字this.max_times = this.times;this.ans.clear();this.ans.add(cur.val);}this.pre = cur;//右this.dfs(cur.right);}
}
二叉树的最近公共祖先
题目详细:LeetCode.236
由题可知:
- 所有节点的值都是唯一的
- p、q 均存在于给定的二叉树中
一个节点也可以是它自己的祖先
所以我们可以先分析当前节点为最近公共祖先的情况有哪些(也就是如何判断该节点是否是p、q的最近公共祖先):
- 情况一: p 和 q 分别在左子树和右子树,那么当前节点即为最近公共祖先,直接返回 root
- 情况二:在右子树中找不到 p 或 q ( right == null ),那么说明 p 和 q 应都在左子树上,返回 left,在左子树中继续寻找
- 情况三:在左子树中找不到 p 或 q ( left == null ),那么说明 p 和 q 应都在右子树上,返回 right,在右子树中继续寻找
若我们基于深度优先遍历的递归算法进行解题,那么还会出现一种情况:
- 假如当 p 与当前节点相同时(p == root),那么 q 必然只能分布在其子树中,所以当前节点即为最近公共祖先,同理可得当(q == root)的情况。
通过分析最近公共祖先的三种基本情况,可知解题的关键在于递归分析节点 p 和 q 在每一个节点的左右子树分布情况
,所以我们可以利用递归算法,优先对当前节点的左右子树进行深度优先遍历,通过左右子树的返回结果来确定当前节点是否为最近公共祖先。
Java解法(递归):
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || p == root || q ==root)return root;TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);return (right == null) ? left : (left == null) ? right : root;}
}
相关文章:
【代码随想录训练营】【Day21】第六章|二叉树|530.二叉搜索树的最小绝对差|501.二叉搜索树中的众数|236. 二叉树的最近公共祖先
二叉搜索树的最小绝对差 题目详细:LeetCode.530 这道题使我第一次了解到二叉树的双指针遍历法,详细可以先查看卡哥的讲解视频:《代码随想录 — 二叉搜索树中的众数》 利用二叉搜索树的特点: 中序遍历二叉搜索树得到一个有序序…...

leaflet 导出图片,打印图片(A4横版或竖版)
第093个 点击查看专栏目录 本示例的目的是介绍如何在vue+leaflet中打印图片导出图片。一个简单的leaflet插件示例,添加了一个图标来打印或导出地图。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果. 文章目录 示例效果配置方式示例源代码(共85行)安装插…...

Java面向对象:继承特性的学习
本文介绍了面向对象的继承特性: 什么是继承 继承的概念 Java中继承的语法 在继承下父类成员的访问 super和this关键字 父类和子类构造方法 在继承下类中出现初始化代码的执行顺序 父类成员的访问权限对子类的可见性 Java的继承关系 final关键字 认识继承和组合关系 继承特性的学…...

问答系统(QA)调研
引言 智能问答系统广泛用于回答人们以自然语言形式提出的问题,经典应用场景包括:智能语音交互、在线客服、知识获取、情感类聊天等。根据QA任务,可以将QA大致分为5大类,分别为: 文本问答(text-based QA&am…...

商务租车的三大优势吸引企业以租代购
随着社会机经济的高速发展,租车模式的日益盛行,租车不仅仅是受个体户的青睐,而作为环保经济的出行方式也让越来越多的企业开始选择以租代买,据调查统计,最早开始商务租车的群体是外企。而近几年,国内的很多…...

蓝桥杯的比赛流程和必考点
蓝桥杯的比赛流程和必考点 距省赛仅1个多月!蓝桥杯的比赛流程和必考点,你还不清楚? “巷子里的猫很自由,却没有归宿;围墙里的狗有归宿,终身都得低头。人生这道选择题,怎么选都会有遗憾。” 但不…...

【数据结构】红黑树
红黑树一、红黑树的概念二、红黑树的接口2.1 插入三、验证四、源码一、红黑树的概念 红黑树也是一个二叉搜索树,他是通过对任何一条从根到叶子的路径上各个结点着色方式的限制,最长路径长度不超过最短路径长度的 2 倍保持近似平衡。他在每个节点添加了一…...
从C++的角度理解C#的Event
由于技术背景是C起家的,所以对于C的概念很清楚,遇到C#的EVENT时候,总感觉这个概念比较抽象,不容易理解,但是当使用函数指针和回调函数来理解EVENT的时候,这个概念就清晰了。 首先对于EVENT来讲,…...

商城进货记录交易-课后程序(JAVA基础案例教程-黑马程序员编著-第七章-课后作业)
【实验7-2】商城进货记录交易 【任务介绍】 1.任务描述 每个商城都需要进货,而这些进货记录整理起来很不方便,本案例要求编写一个商城进货记录交易的程序,使用字节流将商场的进货信息记录在本地的csv文件中。程序具体要求如下: …...

【正点原子FPGA连载】第十七章双核AMP实验 摘自【正点原子】DFZU2EG_4EV MPSoC之嵌入式Vitis开发指南
1)实验平台:正点原子MPSoC开发板 2)平台购买地址:https://detail.tmall.com/item.htm?id692450874670 3)全套实验源码手册视频下载地址: http://www.openedv.com/thread-340252-1-1.html 第十七章双核AMP…...

内存管理框架---页(一)
文章目录物理内存的模型非一致内存访问--NUMA一致内存访问模型--UMA内存管理架构页页框管理页描述符页描述符字段flags字段详解gfp_mask 标志获得页alloc_pages__get_free_pages获得填充为0的页释放页kmallocvmalloc参考资料你用心写的每一篇文章,可能会带别人和自己…...
华为OD机试真题Python实现【流水线】真题+解题思路+代码(20222023)
流水线 题目 一个工厂有m条流水线 来并行完成n个独立的作业 该工厂设置了一个调度系统 在安排作业时,总是优先执行处理时间最短的作业 现给定流水线个数m 需要完成的作业数n 每个作业的处理时间分别为 t1,t2...tn 请你编程计算处理完所有作业的耗时为多少 当n > m时 首先…...

「JVM 编译优化」Graal 编译器
文章目录1. 历史背景2. 构建编译调试环境3. JVMCI 编译器接口4. 代码中间表示5. 代码优化与生成1. 历史背景 Graal 编译器在 JDK 9 以 Jaotc 提前编译工具的形式首次加入到官方的 JDK 中,JDK 10 开始提供替换(得益于 HotSpot 编译器接口,Jav…...

蓝牙标签操作指南
一、APP安装指南 1.APP权限问题 电子标签APP安装之后,会提示一些权限的申请,点击允许。否则某些会影响APP的正常运行。安装后,搜索不到蓝牙标签,可以关闭App,重新打开。 2.手机功能 运行APP时候,需要打开…...

嵌入式 Linux Shell编程
目录 1、shell脚本 2、执行shell脚本 3、shell脚本编写 3.1 shell变量 3.2 标准变量或环境变量 3.4 变量赋值有五种格式 3.5 运算符和表达式 关系运算符 布尔运算符 3.6 Test命令用法 1、判断表达式 2、判断字符串 3.判断整数 4、判断文件 3.7 数组 1、数组定义…...

Web前端学习:一
编辑器的基础使用 编辑器推荐使用: HBuilderx(免费中文)(建议使用) Sublime(免费英文) Sublime中文设置方法,下载语言插件: 1、进入Sublime后,ShiftCtrlP…...

SpringBoot集成Redis实现分布式会话
在单体应用的时代,Session 会话直接保存在服务器中,实现非常简单,但是随着微服务的流行,现代应用架构基本都是分布式架构,请求随机的分配到后端的多个应用中,此时session就需要共享,而存储在red…...

2023年关于身份安全的4 个预测
如果您身处技术领域,就会知道现在是时候盘点过去的一年,展望未来 365 天将影响业务、创新以及我们工作方式的因素的季节。这不是一门精确的科学,我们也不总是对的。但是推测很有趣,当我们看到其中一些趋势成为现实时会更有趣。本文…...

Linux期末考试应急
Linux期末考试应急 虚拟机添加硬盘、分区、格式化、挂载、卸载 fdisk -l#查看系统现有分区fdisk <指定磁盘>#指定磁盘分区sudo mkfs.ext3 <指定分区>#格式化磁盘###挂载磁盘1.新建一个目录sudo mkdir /mnt/test2.将指定分区挂载到对应目录sudo mount /dev/sdb10 /…...

mars3d对geojson图层分属性设置样式
开发中可能会遇到如下需求,在全省的数据中按某个属性⾼亮展示某市区。此时就需要使⽤分属性样式的api了。⽂档如下。GeoJsonLayer - Mars3D API文档属性是根据⽮量数据的属性进⾏匹配。可以通过 layer.graphics[0]?.attr ⽅式获取。 指导有哪些属性之后先设置…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...

Modbus转Ethernet IP深度解析:磨粉设备效率跃升的底层技术密码
在建材矿粉磨系统中,开疆智能Modbus转Ethernet IP网关KJ-EIP-101的应用案例是一个重要的技术革新。这个转换过程涉及到两种主要的通信协议:Modbus和Ethernet IP。Modbus是一种串行通信协议,广泛应用于工业控制系统中。它简单、易于部署和维护…...
Spring Boot SQL数据库功能详解
Spring Boot自动配置与数据源管理 数据源自动配置机制 当在Spring Boot项目中添加数据库驱动依赖(如org.postgresql:postgresql)后,应用启动时自动配置系统会尝试创建DataSource实现。开发者只需提供基础连接信息: 数据库URL格…...