代码随想录算法训练营43期 | Day 18——530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数

本文主要是介绍代码随想录算法训练营43期 | Day 18——530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码随想录算法训练营

  • 代码随想录算法训练营43期 | Day 18
  • 530.二叉搜索树的最小绝对差
    • 解题思路
  • 501.二叉搜索树中的众数
  • 236. 二叉树的最近公共祖先

代码随想录算法训练营43期 | Day 18

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

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。

解题思路

双指针实现二叉搜索树相邻节点的最小绝对值差
二叉搜索树:有序的序列
中序遍历:得到的是有序的数列
将二叉搜索树得到有序的数组,在求两个元素的最小绝对差

class Solution {
public:vector<int> result;void traversal(TreeNode* root){if(root==nullptr) return;//遍历 左traversal(root->left);result.push_back(root->val);traversal(root->right);}int getMinimumDifference(TreeNode* root) {traversal(root);//判断数组中是否含有数组长度<2if(result.size()<2) return 0;//遍历数组int res = INT_MAX;for(int i=1;i<result.size();i++){res = min(res, result[i]-result[i-1]);}return res;}
};

** 方法二 :利用两个指针:**
如何控制两个指针,遍历二叉搜索树

class Solution {
public://记录相邻节点绝对值最小值int result = INT_MAX;TreeNode* pre = nullptr;//函数参数和返回值void traversal(TreeNode* cur){if(cur==nullptr) return ;//左遍历traversal(cur->left);//中的处理逻辑if(pre!=nullptr){result = min(result, cur->val-pre->val);}pre = cur;//右遍历traversal(cur->right);}int getMinimumDifference(TreeNode* root) {traversal(root);return result;}
};

501.二叉搜索树中的众数

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

  1. 结点左子树中所含结点的值小于等于当前结点的值
  2. 结点右子树中所含结点的值大于等于当前结点的值
  3. 左子树和右子树都是二叉搜索树

中序遍历,得到的一个有序的序列,然后从扫描这个中序遍历序列,然后用一个哈希表来统计每个数字出现的个数,这样就可以找到出现次数最多的数字。

但是,这样一颗二叉搜索树的中序遍历序列是 {−1,0,0,1,2,2}。

我们可以发现重复出现的数字一定是一个连续出现的,例如这里的 0 和 2,它们都重复出现了,并且所有的 0 都集中在一个连续的段内,所有的 2 也集中在一个连续的段内。

我们可以顺序扫描中序遍历序列,用 base 记录当前的数字,用 count 记录当前数字重复的次数,用 maxCount 来维护已经扫描过的数当中出现最多的那个数字的出现次数,用 answer 数组记录出现的众数。每次扫描到一个新的元素:

  • 首先更新 base 和 count:
    如果该元素和 base 相等,那么 count 自增 1;
    否则将 base 更新为当前数字,count 复位为 1。
  • 然后更新 maxCount:
    如果 count=maxCount,那么说明当前的这个数字(base)出现的次数等于当前众数出现的次数,将 base 加入 answer 数组;
    如果 count>maxCount,那么说明当前的这个数字(base)出现的次数大于当前众数出现的次数,因此,我们需要将 maxCount 更新为 count,清空 answer 数组后将 base 加入 answer 数组。
class Solution {
private:int maxCount = 0; // 所有元素最大频率int count = 0; // 统计单个元素频率TreeNode* pre = NULL;vector<int> result;void searchBST(TreeNode* cur) {if (cur == NULL) return ;searchBST(cur->left);       // 左// 中if (pre == NULL) { // 第一个节点count = 1;} else if (pre->val == cur->val) { // 与前一个节点数值相同count++;} else { // 与前一个节点数值不同count = 1;}pre = cur; // 更新上一个节点if (count == maxCount) { // 如果和最大值相同,放进result中result.push_back(cur->val);}if (count > maxCount) { // 如果计数大于最大值频率maxCount = count;   // 更新最大频率result.clear();     // 很关键的一步,不要忘记清空result,之前result里的元素都失效了result.push_back(cur->val);}searchBST(cur->right);      // 右return ;}public:vector<int> findMode(TreeNode* root) {count = 0;maxCount = 0;pre = NULL; // 记录前一个节点result.clear();searchBST(root);return result;}
};

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

这篇关于代码随想录算法训练营43期 | Day 18——530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1119009

相关文章

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当