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

news/2024/3/29 5:32:25/文章来源:https://blog.csdn.net/weixin_42764266/article/details/129154971

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_72600.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Npde.js】express以及nodemon

express初始Express什么是Express不使用Express可以创建web服务器吗&#xff1f;Express能做什么安装Express监听GET请求和post请求获取URL中携带的查询参数获取URL中携带的动态参数托管静态资源nodemon为什么使用nodemon初始Express 什么是Express 官方给出的概念&#xff0…

Vue3 基础

Vue3 基础 概述 Vue (发音为 /vjuː/&#xff0c;类似 view) 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建&#xff0c;并提供了一套声明式的、组件化的编程模型&#xff0c;帮助你高效地开发用户界面。无论是简单还是复杂的界面&…

Java:Java与Python — 编码大战

Java和Python是目前市场上最热门的两种编程语言&#xff0c;因为它们具有通用性、高效性和自动化能力。两种语言都有各自的优点和缺点&#xff0c;但主要区别在于Java 是静态类型的&#xff0c;Python是动态类型的。它们有相似之处&#xff0c;因为它们都采用了“一切都是对象”…

单片机输入输出模式

单片机输入输出模式输入模式模拟输入、浮空输入、上拉输入、下拉输入GPIO输出模式推挽输出、开漏输出、复用推挽输出、复用开漏输出。上下拉电阻上拉电阻下拉电阻输入模式 模拟输入、浮空输入、上拉输入、下拉输入 模拟输入&#xff1a;I/O端口的模拟信号&#xff08;电压信号…

日志收集笔记(架构设计、Log4j2项目初始化、Lombok)

1 架构设计 ELK 技术栈架构设计图&#xff1a; 从左往右看&#xff0c; Beats&#xff1a;主要是使用 Filebeat&#xff0c;用于收集日志&#xff0c;将收集后的日志数据发送给 Kafka&#xff0c;充当 Kafka 的生产者Kafka&#xff1a;高性能消息队列&#xff0c;主要起缓冲…

关于客户背景调查的两个案例,说下我的真实看法

这篇文章我只是想客观陈述下事实&#xff0c;并没有对他人的贬低与对自己的吹捧之意。只是想通过这样两件小事&#xff0c;传递出来一个观点&#xff1a;在外贸业务开发过程中&#xff0c;很多时候正是那些我们内心抗拒&#xff0c;不愿意沉下心去做的事&#xff0c;才给了我们…

C#与三菱PLC MC协议通信,Java与三菱PLC MC协议通信

三菱PLC的MC协议是一种常用的通信协议&#xff0c;用于实现三菱PLC与其他设备之间的通信。以下是一些关于MC协议的基本信息&#xff1a;协议格式MC协议的通信数据格式如下&#xff1a;数据头网络编号PC编号目标模块IO编号目标模块站号本机模块IO编号本机模块站号请求数据长度请…

嵌套走马灯Carousel

Carousel 的应用很广泛&#xff0c;基础用法这里不多做阐述&#xff0c;感兴趣的可以去element-gui了解Carousel 组件。 今天主要是梳理嵌套走马灯的逻辑&#xff0c;背景如下&#xff1a; 需要对项目做一个展示&#xff0c;项目可能有一个或多个&#xff0c;同时一个项目可能…

初探 qiling ( 麒麟 ):开源的二进制分析、高级代码模拟框架

官方介绍&#xff1a; 官网&#xff1a;https://qiling.io/&#xff1a;https://twitter.com/qiling_iogithub 地址&#xff1a;https://github.com/qilingframework/qiling 1、qiling 简介 qiling 是什么 qiling 基于 python 开发&#xff0c;是一个开源的、可模拟多种架构…

Web前端:全栈开发人员的责任

多年来&#xff0c;关于全栈开发人员有很多说法&#xff0c;全栈开发人员是一位精通应用程序全栈开发过程的专业人士。这包括数据库、API、前端技术、后端开发语言和控制系统版本。你一定遇到过前端和后端开发人员。前端开发人员将构建接口&#xff0c;而后端开发人员将开发、更…

狂神说:方法

何为方法方法是语句和集合&#xff0c;一起执行一个功能【实际上方法就是函数&#xff0c;说法不一样而已】定义方法加了static才能被main方法调用修饰符&#xff08;public static&#xff09; 返回类型 方法名&#xff08;参数类型 参数名&#xff09;// main方法public stat…

vscode SSH 保存密码自动登录服务器

先在win local上拿到秘钥&#xff0c;然后再把这秘钥copy 进服务器 1. 创建 RSA 密钥对 第一步是在客户端机器&#xff08;通常是您的计算机 win 10&#xff09;上创建密钥对&#xff1a;打开powershell, 输入 ssh-keygen默认情况下ssh-keygen将创建一个 2048 位 RSA 密钥对…

“双碳”目标下二氧化碳地质封存技术应用前景及模型构建实践方法与讨论

我国二氧化碳地质封存技术起步较晚&#xff0c;目前仍没有一套相对完整的行业规范&#xff1b;且就该技术而言&#xff0c;涉及环节众多&#xff0c;理论相对复杂&#xff0c;对于行业的新入局者不太友好。因此&#xff0c;结合时代背景&#xff0c;我们首次尝试对二氧化碳地质…

nodejs出现require is not defined和__dirname is not define 错误

参阅此&#xff0c; Cesium环境搭建成功和初步看一下它的示例_bcbobo21cn的博客-CSDN博客 运行Cesium入门示例&#xff0c;出现下图错误&#xff0c;根据资料&#xff0c;这是node版本的问题&#xff1b; 解决方法是&#xff0c;在server.js头部加入&#xff0c; import { cre…

Flink04: Flink核心API之DataStream

一、Flink 4种不同层次的API Flink中提供了4种不同层次的API&#xff0c;每种API在简洁和易表达之间有自己的权衡&#xff0c;适用于不同的场景。目前上面3个会用得比较多。 • 低级API(Stateful Stream Processing)&#xff1a;提供了对时间和状态的细粒度控制&#x…

Endless lseek导致的SQL异常

最近碰到同事咨询的一个问题&#xff0c;在执行一个函数时&#xff0c;发现会一直卡在那里。 strace抓了下发现会话一直在执行lseek&#xff0c;大致情况如下&#xff1a; 16:13:55.451832 lseek(33, 0, SEEK_END) 1368064 <0.000037> 16:13:55.477216 lseek(33, 0, SE…

linux下安装mongoDB

一、下载mongoDB包 下载地址&#xff1a; https://www.mongodb.com/try/download/community 个人建议&#xff1a;如果是学习阶段&#xff0c;使用5以下版本更好些。 二、安装及配置 1、安装 # 1、解压 $ tar -zxvf mongodb-linux-x86_64-rhel70-4.4.19-rc1.tgz# 2、迁移目…

【音视频处理】为什么MP3不是无损音乐?音频参数详解,码率、采样率、音频帧、位深度、声道、编码格式的关系

大家好&#xff0c;欢迎来到停止重构的频道。上期我们讨论了视频的相关概念&#xff0c;本期我们讨论音频的相关概念。包括采样率、码率、单双声道、音频帧、编码格式等概念。这里先抛出一个关于无损音频的问题。为什么48KHz采样率的.mp3不是无损音乐 &#xff0c;而48KHz采样率…

高性能爬虫之单线程、多进程、多线程的使用,线程池、进程池、协程池的使用

目录一、单线程爬虫代码实现二、 多线程爬虫1、多线程的方法使用2、队列模块的使用3、多线程实现思路剖析4、代码实现**注意点&#xff1a;**三、多进程爬虫1、多进程程的方法使用2、多进程中队列的使用3 代码实现**小结**四、线程池实现爬虫1、线程池使用方法介绍2、使用线程池…

365天深度学习训练营-第J3周:DenseNet算法实战与解析

目录 一、前言 二、论文解读 1、DenseNet的优势 2、设计理念 3、网络结构 4、与其他算法进行对比 三、代码复现 1、使用Pytorch实现DenseNet 2、使用Tensorflow实现DenseNet网络 四、分析总结 一、前言 &#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习…