当前位置: 首页 > 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>…...

03-Open code MCP 与工具调用

03-MCP 与工具调用 掌握 OpenCode 中 MCP&#xff08;Model Context Protocol&#xff09;服务器的配置和使用&#xff0c;扩展 AI 的工具能力。 一、MCP 概述 1.1 什么是 MCP MCP&#xff08;Model Context Protocol&#xff09;是一种标准化协议&#xff0c;允许 AI 模型与…...

Qwen3.5-9B实战教程:app.py添加流式输出支持+前端loading状态优化

Qwen3.5-9B实战教程&#xff1a;app.py添加流式输出支持前端loading状态优化 1. 项目概述 Qwen3.5-9B是一款拥有90亿参数的开源大语言模型&#xff0c;具备强大的逻辑推理、代码生成和多轮对话能力。该模型支持多模态理解&#xff08;图文输入&#xff09;和长上下文处理&…...

Dify 1.0.1升级后Ollama模型添加失败?手把手教你解决Internal Server Error

Dify 1.0.1升级后Ollama模型集成故障排查指南 最近在升级Dify到1.0.1版本后&#xff0c;不少开发者反馈通过Ollama添加模型时遇到无响应或Internal Server Error的问题。作为一名经历过同样困扰的技术实践者&#xff0c;我将在本文分享完整的排查思路和解决方案。 1. 问题现象与…...

Obsidian插件实战:5个提升笔记效率的神器(附避坑指南)

Obsidian插件实战&#xff1a;5个提升笔记效率的神器&#xff08;附避坑指南&#xff09; 如果你正在寻找能够真正提升Obsidian笔记效率的插件组合&#xff0c;这篇文章将为你揭示5个经过实战检验的效率神器。不同于泛泛而谈的插件列表&#xff0c;我们聚焦于那些能够形成工作…...

Python MCP接入卡在“handshake timeout”?资深协议工程师教你用Wireshark+自研debug中间件3分钟定位根源

第一章&#xff1a;Python MCP 服务器开发模板 如何实现快速接入Python MCP&#xff08;Model Control Protocol&#xff09;服务器是构建可插拔、标准化模型服务接口的核心组件。为降低接入门槛&#xff0c;我们提供一套轻量级、生产就绪的开发模板&#xff0c;基于 FastAPI 构…...

【时域心法】别用“平滑”谋杀你的闭环!撕碎软件滤波的视觉骗局,直视“相位延迟”的物理死刑

摘要&#xff1a;纯软件思维有着一种对“平滑数据”的病态迷恋。当他们看到夹杂着毛刺和电磁噪声的 ADC 信号时&#xff0c;最本能的反应就是砸下极其粗暴的“滑动平均滤波”或“低通滤波”。他们在上位机屏幕上画出了绝美的平滑曲线&#xff0c;却不知道自己已经亲手切断了系统…...

Navicat Premium 17 创建触发器保姆级教程

前言&#xff1a;触发器是MySQL中极具实用性的数据库对象&#xff0c;核心作用是“当表发生INSERT/UPDATE/DELETE操作时&#xff0c;自动执行预设SQL”&#xff0c;无需手动调用、无需程序介入&#xff0c;常用于自动填充时间、数据同步、日志记录、数据校验等场景。Navicat Pr…...

生物信息学实战:如何用k-mer分析提升基因组测序质量(附Python代码示例)

生物信息学实战&#xff1a;k-mer分析在基因组测序质量提升中的关键作用 基因组测序数据的质量直接影响后续分析的可靠性&#xff0c;而k-mer分析技术正成为生物信息学工具箱中不可或缺的利器。想象一下&#xff0c;当你拿到一批新的测序数据时&#xff0c;如何快速识别其中的低…...

NAT地址映射表详解:如何看懂并优化你的网络转换效率

NAT地址映射表深度解析&#xff1a;从原理到实战优化的完整指南 当你打开手机浏览网页时&#xff0c;是否想过内网设备如何通过有限的公网IP与全球互联网通信&#xff1f;这背后隐藏着一项关键技术——NAT地址转换。不同于教科书式的概念罗列&#xff0c;我们将从真实网络工程师…...

解决鸿蒙方向的Flutter框架版切换问题-当前最新版本3.35.8——工具切换与命令切换

欢迎加入开源鸿蒙跨平台社区&#xff1a; https://openharmonycrossplatform.csdn.net 最新版本的仓库地址&#xff1a; https://gitcode.com/openharmony-tpc/flutter_flutter/tree/oh-3.35.7-release 本地版本非最新版本 我当前的版本是3.27.5。 需要更新到最新的。 升…...