当前位置: 首页 > news >正文

代码随想录算法训练营第21天|● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

二叉搜索树的最小绝对差

题目连接

https://leetcode.cn/problems/minimum-absolute-difference-in-bst/

思路:

利用二叉搜索树的中序遍历的特性,将二叉树转成有序数组,进而求任意两个数的最小绝对差。

代码

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public ArrayList<Integer> list = new ArrayList<>();public void f(TreeNode root) {if (root == null) {return;}f(root.left);list.add(root.val);f(root.right);}public int getMinimumDifference(TreeNode root) {f(root);int res = Integer.MAX_VALUE;for (int i = 0,j=1; i < list.size()&&j< list.size() ; i++,j++) {if(list.get(j)-list.get(i)<res){res=list.get(j)-list.get(i);}}return res;}
}

二叉搜索树中的众数

题目链接

https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/

思路

利用遍历和map将所有的节点及其频率保存起来,最后将频率最高的放入数组、

代码

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public HashMap<Integer, Integer> map = new HashMap<>();public void f(TreeNode root) {if (root == null) {return;}f(root.left);map.put(root.val, map.getOrDefault(root.val, 0) + 1);f(root.right);}public int[] findMode(TreeNode root) {f(root);int max = -1;for (Integer integer : map.keySet()) {if (map.get(integer) > -1) {max=Math.max(max,map.get(integer));}}ArrayList<Integer> list = new ArrayList<>();for (Integer integer : map.keySet()) {if (map.get(integer) == max) {list.add(integer);}}int[] ans = new int[list.size()];for (int i = 0; i < list.size(); i++) {ans[i] = list.get(i);}return ans;}
}

二叉树的最近公共祖先

题目链接

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

思路

利用二叉树的后续遍历实现对二叉树的自下而上的查找
首先最容易想到的一个情况:如果找到一个节点,发现左子树出现结点p,右子树出现节点q,或者 左子树出现结点q,右子树出现节点p,那么该节点就是节点p和q的最近公共祖先。 即情况一:

请添加图片描述

判断逻辑是 如果递归遍历遇到q,就将q返回,遇到p 就将p返回,那么如果 左右子树的返回值都不为空,说明此时的中节点,一定是q 和p 的最近祖先。

情况二:

请添加图片描述

其实情况一 和 情况二 代码实现过程都是一样的,也可以说,实现情况一的逻辑,顺便包含了情况二。

因为遇到 q 或者 p 就返回,这样也包含了 q 或者 p 本身就是 公共祖先的情况。

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null){return null;}if(root==p||root==q){return root;}TreeNode left=lowestCommonAncestor(root.left,p,q);TreeNode right=lowestCommonAncestor(root.right,p,q);if(left!=null&&right!=null){return root;}if(left==null&&right!=null){return right;}if(left!=null&&right==null){return left;}return null;}
}

相关文章:

代码随想录算法训练营第21天|● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

二叉搜索树的最小绝对差 题目连接 https://leetcode.cn/problems/minimum-absolute-difference-in-bst/ 思路&#xff1a; 利用二叉搜索树的中序遍历的特性&#xff0c;将二叉树转成有序数组&#xff0c;进而求任意两个数的最小绝对差。 代码 /*** Definition for a bina…...

K8S中Prometheus+Grafana监控

1.介绍 phometheus:当前一套非常流行的开源监控和报警系统。 运行原理&#xff1a;通过HTTP协议周期性抓取被监控组件的状态。输出被监控组件信息的HTTP接口称为exporter。 常用组件大部分都有exporter可以直接使用&#xff0c;比如haproxy,nginx&#xff0c;Mysql,Linux系统信…...

题解:CF1968F(Equal XOR Segments)

题解&#xff1a;CF1968F&#xff08;Equal XOR Segments&#xff09; 题目翻译&#xff1a;定义一个序列是好&#xff0c;当且仅当可以将其分成大于 1 1 1 份&#xff0c;使得每个部分的异或和相等。现在给定一个长度为 n n n 的序列 a a a&#xff0c;以及 q q q 次查询…...

Python操作MySQL实战

文章导读 本文用于巩固Pymysql操作MySQL与MySQL操作的知识点&#xff0c;实现一个简易的音乐播放器&#xff0c;拟实现的功能包括&#xff1a;用户登录&#xff0c;窗口显示&#xff0c;加载本地音乐&#xff0c;加入和删除播放列表&#xff0c;播放音乐。 点击此处获取参考源…...

【Linux系统】进程间通信

本篇博客整理了进程间通信的方式管道、 system V IPC的原理&#xff0c;结合大量的系统调用接口&#xff0c;和代码示例&#xff0c;旨在让读者透过进程间通信去体会操作系统的设计思想和管理手段。 目录 一、进程间通信 二、管道 1.匿名管道 1.1-通信原理 1.2-系统调用 …...

北大国际医院腹膜后纤维化课题组 多学科协作开辟治疗新径

腹膜后纤维化(Retroperitoneal Fibrosis,简称RPF)是一种罕见的自身免疫性疾病,其核心特征是纤维组织的异常增生与硬化。这种疾病主要影响肾脏下方的腹主动脉和髂动脉区域,增生的纤维组织会逐渐压迫周围的输尿管和下腔静脉,从而导致一系列并发症,包括主动脉瘤、肾功能衰竭等,甚至…...

面试数据库八股文十问十答第七期

面试数据库八股文十问十答第七期 作者&#xff1a;程序员小白条&#xff0c;个人博客 相信看了本文后&#xff0c;对你的面试是有一定帮助的&#xff01;关注专栏后就能收到持续更新&#xff01; ⭐点赞⭐收藏⭐不迷路&#xff01;⭐ 1&#xff09;索引是越多越好吗&#xff…...

【C++题解】1133. 字符串的反码

问题&#xff1a;1133. 字符串的反码 类型&#xff1a;字符串 题目描述&#xff1a; 一个二进制数&#xff0c;将其每一位取反&#xff0c;称之为这个数的反码。下面我们定义一个字符的反码。 如果这是一个小写字符&#xff0c;则它和字符 a 的距离与它的反码和字符 z 的距离…...

【Python编程实战】基于Python语言实现学生信息管理系统

&#x1f3a9; 欢迎来到技术探索的奇幻世界&#x1f468;‍&#x1f4bb; &#x1f4dc; 个人主页&#xff1a;一伦明悦-CSDN博客 ✍&#x1f3fb; 作者简介&#xff1a; C软件开发、Python机器学习爱好者 &#x1f5e3;️ 互动与支持&#xff1a;&#x1f4ac;评论 &…...

AI网络爬虫:批量爬取电视猫上面的《庆余年》分集剧情

电视猫上面有《庆余年》分集剧情&#xff0c;如何批量爬取下来呢&#xff1f; 先找到每集的链接地址&#xff0c;都在这个class"epipage clear"的div标签里面的li标签下面的a标签里面&#xff1a; <a href"/drama/Yy0wHDA/episode">1</a> 这个…...

md5强弱碰撞

一&#xff0c;类型。 1.弱比较 php中的""和""在进行比较时&#xff0c;数字和字符串比较或者涉及到数字内容的字符串&#xff0c;则字符串会被转换为数值并且比较按照数值来进行。按照此理&#xff0c;我们可以上传md5编码后是0e的字符串&#xff0c;在…...

【Docker故障处理篇】运行容器报错“docker: failed to register layer...file exists.”解决方法

【Docker故障处理篇】运行容器报错“docker: failed to register layer...file exists.” 一、Docker环境介绍2.1 本次环境介绍2.2 本次实践介绍二、故障现象2.1 运行容器消失2.2 重新运行容器报错三、故障分析四、故障处理4.1 停止 Docker 服务:4.2 备份重要数据4.3 清理冲突…...

小红书-社区搜索部 (NLP、CV算法实习生) 一面面经

😄 整个流程按如下问题展开,用时60min左右面试官人挺好,前半部分问问题,后半部分coding一道题。 各位有什么问题可以直接评论区留言,24小时内必回信息,放心~ 文章目录 1、自我介绍2、介绍下项目:微信-多模态小视频分类2.1、看你用了cross-att来融合多模态信息,cross…...

解读makefile中的.PHONY

在 Makefile 中&#xff0c;.PHONY 是一个特殊的目标&#xff0c;用于声明伪目标&#xff08;phony target&#xff09;。伪目标是指并不代表实际构建结果的目标&#xff0c;而是用来触发特定动作或命令的标识。通常情况下&#xff0c;.PHONY 会被用来声明一组需要执行的动作&a…...

linux配置防火墙端口

配置防火墙&#xff0c;添加或删除端口&#xff0c;需要有root权限。 防火墙常用命令如下&#xff1a; 1.查看防火墙状态&#xff1a; systemctl status firewalld active(running)&#xff1a;开启状态&#xff0c;正在运行中 inactive(dead)&#xff1a;关闭状态&#xff…...

sklearn线性回归--岭回归

sklearn线性回归--岭回归 岭回归也是一种用于回归的线性模型&#xff0c;因此它的预测公式与普通最小二乘法相同。但在岭回归中&#xff0c;对系数&#xff08;w&#xff09;的选择不仅要在训练数据上得到好的预测结果&#xff0c;而且还要拟合附加约束&#xff0c;使系数尽量小…...

三十一、openlayers官网示例Draw Features解析——在地图上自定义绘制点、线、多边形、圆形并获取图形数据

官网demo地址&#xff1a; Draw Features 先初始化地图&#xff0c;准备一个空的矢量图层&#xff0c;用于显示绘制的图形。 initLayers() {const raster new TileLayer({source: new XYZ({url: "https://server.arcgisonline.com/ArcGIS/rest/services/World_Imagery/…...

医疗科技:UWB模块为智能医疗设备带来的变革

随着医疗科技的不断发展和人们健康意识的提高&#xff0c;智能医疗设备的应用越来越广泛。超宽带&#xff08;UWB&#xff09;技术作为一种新兴的定位技术&#xff0c;正在引领着智能医疗设备的变革。UWB模块作为UWB技术的核心组成部分&#xff0c;在智能医疗设备中发挥着越来越…...

Java面试题大全(从基础到框架,中间件,持续更新~~~)

从Java基础到数据库&#xff0c;Spring&#xff0c;MyBatis&#xff0c;消息中间件&#xff0c;微服务解决全部Java面试过程中的问题。&#xff08;持续更新~~&#xff09; Java基础 2024最新Java面试题——java基础 MySQL基础 mysql基础知识——适合不太熟悉数据库知识的小…...

零知识证明在隐私保护和身份验证中的应用

PrimiHub一款由密码学专家团队打造的开源隐私计算平台&#xff0c;专注于分享数据安全、密码学、联邦学习、同态加密等隐私计算领域的技术和内容。 隐私保护和身份验证是现代社会中的关键问题&#xff0c;尤其是在数字化时代。零知识证明&#xff08;Zero-Knowledge Proofs&…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...