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

代码随想录【Day21】| 530. 二叉搜索树的最小绝对差、501. 二叉搜索树中的众数、236. 二叉树的最近公共祖先

530. 二叉搜索树的最小绝对差

题目链接

题目描述:
给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。

示例:
在这里插入图片描述
提示:树中至少有 2 个节点。

难点:

解答错误!仅考虑了相邻,漏掉了不相邻的情况(与根节点之差!)

class Solution {public int getMinimumDifference(TreeNode root) {//最小差值一定是相邻接的节点,子树某个根节点和左(右)孩子//采用中序遍历就可以if (root == null) return Integer.MAX_VALUE;int left, right;if (root.left != null) {left = Math.min(getMinimumDifference(root.left), root.val - root.left.val);}else {left = Integer.MAX_VALUE;}if (root.right != null) {right = Math.min(getMinimumDifference(root.right), root.right.val - root.val);}else {right = Integer.MAX_VALUE;}return Math.min(left, right);}
}

在中序遍历中,要记录上一个遍历的节点!

class Solution {TreeNode pre;int result = Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {//采用中序遍历traversal(root);return result;}private void traversal(TreeNode root) {if (root == null) return;traversal(root.left);if (pre != null) {result = Math.min(result, root.val - pre.val);}pre = root;traversal(root.right);}
}

时长:
15min

收获:
中序遍历,记录上一个遍历的节点


501. 二叉搜索树中的众数

题目链接

题目描述:
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

假定 BST 有如下定义:

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如:

给定 BST [1,null,2,2],
在这里插入图片描述
返回[2].

提示:如果众数超过1个,不需考虑输出顺序

进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)

难点:

思路:

时间复杂度:O()
空间复杂度:O()

class Solution {int cnt;int maxNum;TreeNode pre;List<Integer> result = new ArrayList<>();public int[] findMode(TreeNode root) {searchBST(root);return result.stream().mapToInt(Integer::intValue).toArray();}private void searchBST(TreeNode root) {if (root == null) return;searchBST(root.left);if (pre == null) { //第一个节点cnt = 1;}else if(pre.val == root.val) { //相同值,计数cnt++;}else { //不同值,计数器重置1cnt = 1;}pre = root;if (cnt == maxNum) {result.add(root.val);}if (cnt > maxNum) {result.clear();result.add(root.val);maxNum = cnt;}searchBST(root.right);}
}

时长:
22min

收获:
使用双指针,记录上一个遍历的节点

将ArrayList< Integer >转化为int[]数组的方式:
result.stream().mapToInt(Integer::intValue).toArray();


236. 二叉树的最近公共祖先

题目链接

题目描述:
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
在这里插入图片描述
示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

难点:

思路:

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == p || root == q || root == null) 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;}
}

时长:
20min

收获:
有难度的一题,思路好好再捋一捋

相关文章:

代码随想录【Day21】| 530. 二叉搜索树的最小绝对差、501. 二叉搜索树中的众数、236. 二叉树的最近公共祖先

530. 二叉搜索树的最小绝对差 题目链接 题目描述&#xff1a; 给你一棵所有节点为非负值的二叉搜索树&#xff0c;请你计算树中任意两节点的差的绝对值的最小值。 示例&#xff1a; 提示&#xff1a;树中至少有 2 个节点。 难点&#xff1a; 解答错误&#xff01;仅考虑了…...

注意啦,面试通过后,别忘了教师资格证认定

所有要「教师资格证认定」教程的宝子们看过来面试合格的小伙伴都可以进行认定工作 . 认定时间 查询各省份认定公告&#xff0c;确定认定时间范围。以下是公告汇总网址&#xff08;https://www.jszg.edu.cn/portal/qualification_cert/dynamics?id21691&#xff09; 认定次数 每…...

【LeetCode】No.154. 寻找旋转排序数组中的最小值 II -- Java Version

题目链接&#xff1a;https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/ 1. 题目介绍&#xff08;154. 寻找旋转排序数组中的最小值 II&#xff09; 已知一个长度为 n 的数组&#xff0c;预先按照升序排列&#xff0c;经由 1 到 n 次 旋转 后&#xff0…...

RestTemplate远程调用

我们现在项目中使用的RPC远程调用技术是Dubbo实际上除了Dubbo技术之外,还有很多远程调用的方法它们有些调用的思想都和Dubbo完全不同Dubbo是SpringCloudAlibaba提供的功能强大的RPC框架但是Dubbo功能也有限制,如果我们想调用的方法不是我们当前项目的组件或功能,甚至想调用的方…...

registerForActivityResult使用

目录 针对 activity 结果注册回调 启动 activity 以获取其结果 在单独的类中接收 activity 结果 测试 创建自定义协定 registerForActivityResult()是startActivityForResult&#xff08;&#xff09;的替代&#xff0c;简化了数据回调的写法 启动另一个 activity&#x…...

工作中,python真的有用吗?

普通上班族学Python有用吗&#xff1f; 那么&#xff0c;我也在这里提出一个问题&#xff1a;Python究竟适不适合办公人士来学习&#xff0c;以及学了之后究竟能不能给我的工作来带质一般的飞跃&#xff1f; 以我的亲身经历为例&#xff0c;我可以很负责的告诉大家&#xff0c…...

固态继电器控制电路

固态继电器控制电路 固态继电器&#xff08;SSR&#xff09;的种类和型号很多&#xff0c;因此其输入控制方法和控制电路也相应众多。固态继电器&#xff08;SSR&#xff09;的共同特点在于驱动电流或驱动电压小&#xff0c;即只需输入一个小信号即可控制SSR的开关。 如果需要…...

数仓、数据湖、湖仓一体、数据网格的探索与研究

第一代&#xff1a;数据仓库 定义 为解决数据库面对数据分析的不足&#xff0c;孕育出新一类产品数据仓库。数据仓库&#xff08;Data Warehouse&#xff09;是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合&#xff0c;用于支持管理决策和信息的全局共享。 数…...

设计模式系列 - 备忘录模式

介绍&定义 备忘录模式&#xff0c;也叫快照&#xff08;Snapshot&#xff09;模式&#xff0c;英文翻译是 Memento Design Pattern。在 GoF 的《设计模式》一书中&#xff0c;备忘录模式是这么定义的&#xff1a; Captures and externalizes an object’s internal state…...

详细介绍React生命周期和diffing算法

事件处理 1.通过onXxx属性指定事件处理函数(注意大小写) React使用的是自定义(合成)事件, 而不是使用的原生DOM事件 —— 为了更好的兼容性&#xff1b;React中的事件是通过事件委托方式处理的(委托给组件最外层的元素) ——为了的高效。 2.通过event.target得到发生事件的DOM…...

面向对象的特点

1、什么是对象对象的含义是指具体的某一个事物&#xff0c;即在现实生活中能够看得见摸得着的事物。在面向对象程序设计中&#xff0c;对象所指的是计算机系统中的某一个成分。在面向对象程序设计中&#xff0c;对象包含两个含义&#xff0c;其中一个是数据&#xff0c;另外一个…...

智慧校园平台源码 智慧教务 智慧电子班牌系统

系统介绍 智慧校园系统是通过信息化手段,实现对校园内各类资源的有效集成 整合和优化&#xff0c;实现资源的有效配置和充分利用&#xff0c;将校务管理过程的优化协调。为校园提供数字化教学、数字化学习、数字化科研和数字化管理。 致力于为家长和教师提供一个全方位、多层…...

Vue篇.03-组合式API [setup()]

单文件组件(1)<script setup><script setup> 是在单文件组件 (SFC) 中使用组合式 API 的编译时语法糖。当同时使用 SFC 与组合式 API 时该语法是默认推荐启用该语法&#xff0c;需要在 <script> 代码块上添加 setup attribute, 里面的代码会被编译成组件 s…...

QHashIterator-官翻

QHashIterator Class template <typename Key, typename T> class QHashIterator QHashIterator 类为 QHash 和 QMultiHash 提供 Java 风格的常量迭代器。更多内容… 头文件:#include qmake:QT core 所有成员列表&#xff0c;包括继承的成员废弃的成员 公共成员函数…...

[qiankun]-部署后线上问题

[qiankun]-部署后线上问题微服务加载问题-现象1现象描述问题分析解决方案微服务加载问题-现象2现象描述问题分析微服务加载问题-现象3现象描述分析解决方案属于项目打包后&#xff0c;部署到服务器上&#xff0c;所遇到的部分问题 微服务加载问题-现象1 现象描述 项目部署实…...

位图数组 布隆过滤器

文章目录位图数组获取索引获取索引状态设置索引状态布隆过滤器特点大致原理位图数组 一个int类型的整数用4字节,也就是32个bit位来表示&#xff0c;将整数类型的数组转换成位图数组&#xff0c;那么存储长度将变为原来的32倍 arr[0] 表示0-31 arr[1] 表示32-63 //...获取索引…...

多线程Thread常用方法和状态

Thread类 及常见方法 1、常见构造方法 方法说明Thread()创建线程对象Thread(Runnable target)使用 Runnable 对象创建线程对象Thread(String name)创建线程对象&#xff0c;并命名Thread(Runnable target, String name)使用 Runnable 对象创建线程对象&#xff0c;并命名Thre…...

Codeforces Round #836 (Div. 2)

A SSeeeeiinngg DDoouubbllee 题意&#xff1a;告诉你一个字符串。若该串上每一位上的字母都可以出现两次&#xff0c;求回文串 思路&#xff1a;正向再反向输出s即可 #include <bits/stdc.h> #define lowbit(x) x&(-x) #define ios cin.sync_with_stdio(false)…...

Python学习之项目实践: 写一个MP3播放器

下面呢&#xff0c;是一个 Python MP3 播放器&#xff0c;它使用 pygame 模块来实现音乐播放功能&#xff1a; import pygame class MP3Player: """ MP3 播放器类 """ def __init__(self): pygame.mixer.init() def play(self, file_path): &quo…...

RocketMQTemplate 实现消息发送

代码托管于gitee&#xff1a;easy-rocketmq 文章目录一、前置工作二、消费者三、生产者1. 普通消息2. 过滤消息3. 同步消息4. 延时消息5. 批量消息6. 异步消息7. 单向消息8. 顺序消息9. 事务消息概要Demo源码解读一、前置工作 1、导入依赖 <dependency><groupId>…...

如何利用 SEO 优化平台提高网站排名

如何利用 SEO 优化平台提高网站排名 在当前数字化时代&#xff0c;网站排名是吸引流量、提升业务的重要因素。搜索引擎优化&#xff08;SEO&#xff09;在这一过程中扮演着不可或缺的角色。本文将详细探讨如何利用 SEO 优化平台来提高网站在搜索引擎中的排名&#xff0c;涵盖问…...

零成本上手:在魔塔社区用免费GPU微调InternLM2.5-7B-Chat实战

1. 为什么选择魔塔社区进行大模型微调 第一次接触大模型微调的朋友们可能都有这样的困惑&#xff1a;动辄几十GB的模型参数&#xff0c;没有高端显卡怎么玩得转&#xff1f;这里就要给大家安利一个宝藏平台——阿里魔塔社区。我去年刚开始研究大模型时&#xff0c;也是被硬件门…...

实测!用AI从0到1完成一个项目,需要多少token?

用AI编程工具&#xff0c;从零撸图书管理系统全记录现在全网都在聊AI写项目&#xff0c;但没人说真话&#xff1a;纯靠聊天瞎怼需求&#xff0c;到底浪费多少token&#xff1f;步骤乱不乱&#xff1f;代码能不能直接跑&#xff1f;今天不玩虚的&#xff0c;全程实测飞算JavaAI智…...

HRNet并行架构解析:从多分辨率融合到语义分割实战代码精讲

1. HRNet架构设计精髓&#xff1a;为什么并行结构能吊打传统模型 第一次看到HRNet的论文时&#xff0c;我被它的设计思路彻底惊艳到了。传统网络像ResNet、VGG这些"老前辈"都是串行结构&#xff0c;图像分辨率像滑滑梯一样越来越低。而HRNet却像交响乐团&#xff0c;…...

基于MATLAB与机器学习(SVM)的裂缝检测识别系统,附GUI界面、特征参数计算与Excel...

基于MATLAB和机器学习&#xff08;向量机&#xff09;的裂缝检测&#xff08;识别&#xff09;系统程序&#xff0c;带GUI界面&#xff0c;对裂缝主要参数&#xff08;长度&#xff0c;宽度&#xff0c;面积&#xff09;进行计算&#xff0c;已经训练好分类器&#xff0c;包含裂…...

新手福音!5分钟手把手教你用JSON→C# Entities解决实体类生成难题

大家好&#xff0c;我是CSDN的老用户daier。最近不少读者在后台问我&#xff1a;“后端接口返回一堆JSON数据&#xff0c;要在C#项目里写对应的Model类&#xff0c;太麻烦了&#xff01;嵌套对象、数组、下划线转PascalCase、nullable类型怎么办&#xff1f;” 今天我手把手带…...

如何优化Mars项目中的IndexedDB索引设计:提升移动端Web查询性能的完整指南

如何优化Mars项目中的IndexedDB索引设计&#xff1a;提升移动端Web查询性能的完整指南 【免费下载链接】Mars 腾讯移动 Web 前端知识库 项目地址: https://gitcode.com/gh_mirrors/mar/Mars Mars作为腾讯移动Web前端知识库&#xff0c;提供了丰富的移动端Web开发解决方案…...

基于MATLAB与Simulink的OFDM通信系统性能仿真:包括保护间隔、信道均衡与误比特率...

matlab调制解调 OFDM OTFS 16qam qpsk ldpc turbo在高斯白噪声&#xff0c;频率选择性衰落信道下的误比特率性能仿真&#xff0c;matlab代码 OFDM simulink 包括添加保护间隔&#xff08;cp&#xff09;&#xff0c;信道均衡(ZF MMSE MRC MA LMSEE) 代码每行都有注释&#xff0…...

轻量级跨平台安卓应用安装工具:APK-Installer极简高效使用指南

轻量级跨平台安卓应用安装工具&#xff1a;APK-Installer极简高效使用指南 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer 在Windows系统上运行安卓应用通常面临两大痛…...

像素史诗·智识终端Claude Code实践:自动化代码生成与审查

像素史诗智识终端Claude Code实践&#xff1a;自动化代码生成与审查 1. 开发者的新助手 最近在开发圈里&#xff0c;一个叫"像素史诗智识终端"的工具开始引起关注。它集成了类似Claude Code的智能代码能力&#xff0c;正在改变开发者们日常工作的方式。想象一下&am…...