【代码随想录训练营】【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 ⽅式获取。 指导有哪些属性之后先设置…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...

PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...