day21 ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先
- 二叉搜索树的最小绝对差
二叉搜索树(Binary Search Tree,简称 BST)是一种特殊的二叉树,它的每个节点都满足以下条件:
- 左子树上所有节点的值均小于该节点的值;
- 右子树上所有节点的值均大于该节点的值;
- 左右子树都是二叉搜索树。
因此,对于一棵二叉搜索树,中序遍历得到的结果是一个有序的数组。而本题就是要求在一个二叉搜索树中找到任意两个节点的差的绝对值的最小值。
解题思路:
- 对二叉搜索树进行中序遍历,得到一个有序数组。
- 遍历该有序数组,计算相邻两个元素的差值,找到其中最小的即可。
代码实现:
class Solution {
public:int getMinimumDifference(TreeNode* root) {vector<int> nums; // 中序遍历得到的有序数组inorder(root, nums);int minDiff = INT_MAX;for (int i = 1; i < nums.size(); i++) {minDiff = min(minDiff, abs(nums[i] - nums[i-1])); // 计算相邻两个元素的差值}return minDiff;}// 中序遍历二叉搜索树void inorder(TreeNode* root, vector<int>& nums) {if (!root) return;inorder(root->left, nums);nums.push_back(root->val);inorder(root->right, nums);}
};
时间复杂度:O(n),其中 n 是二叉搜索树中节点的个数。
- 二叉搜索树中的众数
这道题要求我们找到二叉搜索树中出现次数最多的元素。
解题思路:
- 对二叉搜索树进行中序遍历,得到一个有序数组。
- 遍历该有序数组,计算每个元素出现的次数,找到出现次数最多的元素即可。
代码实现:
class Solution {
public:vector<int> findMode(TreeNode* root) {vector<int> nums; // 中序遍历得到的有序数组inorder(root, nums);vector<int> res; // 众数的结果集int maxCount = 0, count = 0;for (int i = 0; i < nums.size(); i++) {count++; // 统计当前元素出现的次数if (i == nums.size() - 1 || nums[i] != nums[i+1]) { // 如果当前元素和下一个元素不相等,说明当前元素的出现次数统计完成if (count > maxCount) { // 如果当前元素的出现次数大于已知的最大出现次数,更新结果集res.clear();res.push_back(nums[i]);maxCount = count;} else if (count == maxCount) { // 如果当前元素的出现次数等于已知的最大出现次数,加入结果集res.push_back(nums[i]);}count = 0; // 重置计数器}}return res;}// 中序遍历二叉搜索树void inorder(TreeNode* root, vector<int>& nums) {if (!root) return;inorder(root->left, nums);nums.push_back(root->val);inorder(root->right, nums);}
};
时间复杂度:O(n),其中 n 是二叉搜索树中节点的个数。
- 二叉树的最近公共祖先
这道题要求我们找到二叉树中任意两个节点的最近公共祖先。
解题思路:
我们可以采用递归的方式来解决该问题。对于当前节点,分别递归遍历其左右子树,如果左子树返回的结果不为空,右子树返回的结果也不为空,则说明当前节点为 p 和 q 的最近公共祖先;如果左子树返回的结果为空,则说明 p 和 q 只可能在右子树中,返回右子树的结果;如果右子树返回的结果为空,则说明 p 和 q 只可能在左子树中,返回左子树的结果。
代码实现:
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (!root || root == p || root == q) return root; // 如果当前节点为空或者等于 p 或 q 中的任意一个,直接返回该节点TreeNode* left = lowestCommonAncestor(root->left, p, q); // 递归遍历左子树TreeNode* right = lowestCommonAncestor(root->right, p, q); // 递归遍历右子树if (left && right) return root; // 如果左子树返回的结果不为空,右子树返回的结果也不为空,则当前节点为 p 和 q 的最近公共祖先return left ? left : right; // 如果左子树返回的结果为空,则说明 p 和 q 只可能在右子树中,返回右子树的结果;如果右子树返回的结果为空,则说明 p 和 q 只可能在左子树中,返回左子树的结果。}
};
时间复杂度:O(n),其中 n 是二叉树中节点的个数。
相关文章:
day21 ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先
二叉搜索树的最小绝对差 二叉搜索树(Binary Search Tree,简称 BST)是一种特殊的二叉树,它的每个节点都满足以下条件: 左子树上所有节点的值均小于该节点的值;右子树上所有节点的值均大于该节点的值&#…...
大学计算机(软件类)专业推荐竞赛 / 证书 官网及赛事相关信息整理
大学计算机专业(软件)推荐竞赛 / 证书 官网及赛事相关信息 一、算法类(丰富简历): 1、ACM国际大学生程序设计竞赛: 官网:https://icpc.global/ 国内:http://icpc.pku.edu.cn/index.htm 报名方式:区域预赛一般每年9-1…...
Metasploit入门到高级【第九章】
预计更新第一章:Metasploit 简介 Metasploit 是什么Metasploit 的历史和发展Metasploit 的组成部分 第二章:Kali Linux 入门 Kali Linux 简介Kali Linux 安装和配置常用命令和工具介绍 第三章:Metasploit 基础 Metasploit 的基本概念Met…...
JDK之8后: 协程? 虚拟线程!!!
特性官方文档: https://openjdk.org/jeps/436 Java协程 近三十年来,Java 开发人员一直依赖线程作为并发服务器应用程序的构建块。每个方法中的每个语句都在线程内执行,并且由于 Java 是多线程的,因此多个执行线程同时发生。线程是Java的并发…...

体验 jeecg
体验 jeecg官网地址事前准备安装升级 node 和 npm 版本验证安装安装 pnpm clidocker 启动 MySQLdocker 启动 redisgit clone 项目启动JAVA项目 jeecg-boot启动Vue3项目 jeecgboot-vue3官网地址 http://www.jeecg.com/ 事前准备 (1) 为了回避Could not find artifact com.mic…...

投稿指南【NO.13】计算机学会CCF推荐期刊和会议分享(人工智能)
前 言国内高等院校研究生及博士毕业条件需要发表高水平期刊或者顶会(清北上交等重点学校毕业要求为至少发一篇顶会),很多同学私信问到一级学会的会议论文怎么找、是什么,比如前段时间放榜的CVPR论文就是人工智能领域的顶会国际会议…...

一份sql笔试
1、 select substr(time,1,10),count(order_id),count(distinct passenger_id) from order where substr(time,1,7)2023-08 group by substr(time,1,10) order by substr(time,1,10);2、 select city_id from (select * from order where substr(time,1,7) 2022-08) t1 left j…...
交换瓶子
交换瓶子 贡献者:programmer_ada 有N个瓶子,编号 1 ~ N,放在架子上。 比如有5个瓶子: 2 1 3 5 4 要求每次拿起2个瓶子,交换它们的位置。 经过若干次后,使得瓶子的序号为: 1 2 3 4 5 对于这么…...
二、Docker安装、启动、卸载、示例
Docker 支持 CentOS 6 及以后的版本,可以直接通过yum进行安装: 使用流程:启动主机 – 启动Docker服务 – 下载容器镜像 – 启动镜像得一个到容器 – 进入容器使用我们想要的程序 主机一般是Linux、Utuban 以下主机系统以CentOS7为例子&#…...

开心档之C++ STL 教程
C STL 教程 目录 C STL 教程 实例 在前面的章节中,我们已经学习了 C 模板的概念。C STL(标准模板库)是一套功能强大的 C 模板类,提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法和数据结构…...
Thread 类的基本用法
文章目录一、线程创建1.1 Thread的常见构造方法2.1 创建线程二、线程中断2.1 Thread的几个常见属性2.2 中断线程三、线程等待四、线程休眠五、获取线程实例一、线程创建 1.1 Thread的常见构造方法 方法说明Thread()创建线程对象Thread(Runnable target)使用Runnable对象创建线…...
2023.3.28 天梯赛训练赛补题(病毒溯源 , 龙龙送外卖 , 红色警报)
文章目录1.病毒溯源问题:求树的最长链长度和字典序最小的最长链思路:2.龙龙送外卖思路:3.红色警报:思路:1.病毒溯源 问题:求树的最长链长度和字典序最小的最长链 思路: 一开始用 bfs 做的 &a…...

917. 仅仅反转字母
917. 仅仅反转字母https://leetcode.cn/problems/reverse-only-letters/ 难度简单189 给你一个字符串 s ,根据下述规则反转字符串: 所有非英文字母保留在原有位置。所有英文字母(小写或大写)位置反转。 返回反转后的 s 。 示例…...

Linux-Git
一、总论 1.1 写在前面的话 这已经是我第三遍学Git相关操作了,可以说这个玩意是真的狗,因为确实用不到,不知道下个学期会不会用到,直到现在我刚刚学完,处于知识水平的巅峰,知道Git的具体功能ÿ…...

leetcode:2273. 移除字母异位词后的结果数组(python3解法)
难度:简单 给你一个下标从 0 开始的字符串 words ,其中 words[i] 由小写英文字符组成。 在一步操作中,需要选出任一下标 i ,从 words 中 删除 words[i] 。其中下标 i 需要同时满足下述两个条件: 0 < i < words.l…...

基于Python长时间序列遥感数据处理及在全球变化、物候提取、植被变绿与固碳分析、生物量估算与趋势分析等领域中的应用
植被是陆地生态系统中最重要的组分之一,也是对气候变化最敏感的组分,其在全球变化过程中起着重要作用,能够指示自然环境中的大气、水、土壤等成分的变化,其年际和季节性变化可以作为地球气候变化的重要指标。此外,由于…...
4.4---Spring框架之Spring事务(复习版本)
Spring事务的本质其实就是数据库对事务的支持,没有数据库的事务支持,spring是无法提供事务功能的。 Spring只提供统一事务管理接口,具体实现都是由各数据库自己实现,数据库事务的提交和回滚是通过 redo log 和 undo log实现的。 S…...

IP-Guard是否支持禁止客户端电脑卸载指定软件?
哪些浏览器支持设置窗口水印? 支持的浏览器有:搜狗浏览器、360安全浏览器、360极速浏览器、qq浏览器、谷歌浏览器、ie浏览器、edge浏览器 注意: 1.目标URL窗口水印不支持Firefox浏览器和猎豹浏览器 2.搜狗浏览器在兼容模式下,目标URL窗口水印不生效 3.部分浏览器(360安全…...

系统图标形状overlayapk
时间:2020/10/10 之前公司不允许csdn,笔记写在其它地方。最近整理过来 1、图标形状的overlay frameworks\base\packages\overlays目录 2、某一种形状的源码 默认配置在framework/base/core/res/res res下面放着图标形状的mask路径,这个值是一个矢量图…...

辅助编程coding的两种工具:Github Copilot、Cursor
目录Cursor简介下载地址:使用技巧:CHAT:example 1:注意:example 2:Github Copilot官网简介以插件方式安装pycharm自动写代码example 1:写一个mysql取数据的类example 2:写一个多重共线性检测的类…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...

vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...

短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...