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

代码随想录阅读笔记-二叉树【二叉搜索树中的众数】

题目

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

假定 BST 有如下定义:

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

例如:

给定 BST [1,null,2,2],

501. 二叉搜索树中的众数

返回[2].

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

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

思路

这道题目如果不是二叉搜索树的话,应该怎么解题,是二叉搜索树,又应该如何解题,两种方式做一个比较,可以加深大家对二叉树的理解。

递归法

如果不是二叉搜索树

如果不是二叉搜索树,最直观的方法一定是把这个树都遍历了,用map统计频率,把频率排个序,最后取前面高频的元素的集合。

具体步骤如下:

1、这个树都遍历了,用map统计频率

至于用前中后序哪种遍历也不重要,因为就是要全遍历一遍,怎么个遍历法都行,层序遍历都没毛病!

这里采用前序遍历,代码如下:

// map<int, int> key:元素,value:出现频率
void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历if (cur == NULL) return ;map[cur->val]++; // 统计元素频率searchBST(cur->left, map);searchBST(cur->right, map);return ;
}

2、把统计的出来的出现频率(即map中的value)排个序

有的同学可能可以想直接对map中的value排序,还真做不到,C++中如果使用std::map或者std::multimap可以对key排序,但不能对value排序。

所以要把map转化数组即vector,再进行排序,当然vector里面放的也是pair<int, int>类型的数据,第一个int为元素,第二个int为出现频率。

bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second; // 按照频率从大到小排序
}vector<pair<int, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp); // 给频率排个序

3、取前面高频的元素

此时数组vector中已经是存放着按照频率排好序的pair,那么把前面高频的元素取出来就可以了。

result.push_back(vec[0].first);
for (int i = 1; i < vec.size(); i++) {// 取最高的放到result数组中if (vec[i].second == vec[0].second) result.push_back(vec[i].first);else break;
}
return result;

整体C++代码如下:

class Solution {
private:void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历if (cur == NULL) return ;map[cur->val]++; // 统计元素频率searchBST(cur->left, map);searchBST(cur->right, map);return ;
}
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;
}
public:vector<int> findMode(TreeNode* root) {unordered_map<int, int> map; // key:元素,value:出现频率vector<int> result;if (root == NULL) return result;searchBST(root, map);vector<pair<int, int>> vec(map.begin(), map.end());sort(vec.begin(), vec.end(), cmp); // 给频率排个序result.push_back(vec[0].first);for (int i = 1; i < vec.size(); i++) {// 取最高的放到result数组中if (vec[i].second == vec[0].second) result.push_back(vec[i].first);else break;}return result;}
};

所以如果本题没有说是二叉搜索树的话,那么就按照上面的思路写!

二叉搜索树

既然是搜索树,它中序遍历就是有序的

如图:

501.二叉搜索树中的众数1

中序遍历代码如下:

void searchBST(TreeNode* cur) {if (cur == NULL) return ;searchBST(cur->left);       // 左(处理节点)                // 中searchBST(cur->right);      // 右return ;
}

遍历有序数组的元素出现频率,从头遍历,那么一定是相邻两个元素作比较,然后就把出现频率最高的元素输出就可以了。

关键是在有序数组上的话,好搞,在树上怎么搞呢?

这就考察对树的操作了。

在上一篇博客中我们就使用了pre指针和cur指针的技巧,这次又用上了。

弄一个指针指向前一个节点,这样每次cur(当前节点)才能和pre(前一个节点)作比较。

而且初始化的时候pre = NULL,这样当pre为NULL时候,我们就知道这是比较的第一个元素。

代码如下:

if (pre == NULL) { // 第一个节点count = 1; // 频率为1
} else if (pre->val == cur->val) { // 与前一个节点数值相同count++;
} else { // 与前一个节点数值不同count = 1;
}
pre = cur; // 更新上一个节点

此时又有问题了,因为要求最大频率的元素集合(注意是集合,不是一个元素,可以有多个众数),如果是数组上大家一般怎么办?

应该是先遍历一遍数组,找出最大频率(maxCount),然后再重新遍历一遍数组把出现频率为maxCount的元素放进集合。(因为众数有多个)

这种方式遍历了两遍数组。

那么我们遍历两遍二叉搜索树,把众数集合算出来也是可以的。

但这里其实只需要遍历一次就可以找到所有的众数。

那么如何只遍历一遍呢?

如果 频率count 等于 maxCount(最大频率),当然要把这个元素加入到结果集中(以下代码为result数组),代码如下:

if (count == maxCount) { // 如果和最大值相同,放进result中result.push_back(cur->val);
}

是不是感觉这里有问题,result怎么能轻易就把元素放进去了呢,万一,这个maxCount此时还不是真正最大频率呢。

所以下面要做如下操作:

频率count 大于 maxCount的时候,不仅要更新maxCount,而且要清空结果集(以下代码为result数组),因为结果集之前的元素都失效了。

if (count > maxCount) { // 如果计数大于最大值maxCount = count;   // 更新最大频率result.clear();     // 很关键的一步,不要忘记清空result,之前result里的元素都失效了result.push_back(cur->val);
}

关键代码都讲完了,完整代码如下:(只需要遍历一遍二叉搜索树,就求出了众数的集合

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;}
};

迭代法

只要把中序遍历转成迭代,中间节点的处理逻辑完全一样。

下面我给出其中的一种中序遍历的迭代法,其中间处理逻辑一点都没有变(我从递归法直接粘过来的代码,连注释都没改)

代码如下:

class Solution {
public:vector<int> findMode(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = NULL;int maxCount = 0; // 最大频率int count = 0; // 统计频率vector<int> result;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点,访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left;                // 左} else {cur = st.top();st.pop();                       // 中if (pre == NULL) { // 第一个节点count = 1;} else if (pre->val == cur->val) { // 与前一个节点数值相同count++;} else { // 与前一个节点数值不同count = 1;}if (count == maxCount) { // 如果和最大值相同,放进result中result.push_back(cur->val);}if (count > maxCount) { // 如果计数大于最大值频率maxCount = count;   // 更新最大频率result.clear();     // 很关键的一步,不要忘记清空result,之前result里的元素都失效了result.push_back(cur->val);}pre = cur;cur = cur->right;               // 右}}return result;}
};

总结

本题在递归法中,给出了如果是普通二叉树,应该怎么求众数。

知道了普通二叉树的做法时候,再进一步给出二叉搜索树又应该怎么求众数,这样鲜明的对比,相信会对二叉树又有更深层次的理解了。

在递归遍历二叉搜索树的过程中还介绍了一个统计最高出现频率元素集合的技巧, 要不然就要遍历两次二叉搜索树才能把这个最高出现频率元素的集合求出来。

为什么没有这个技巧一定要遍历两次呢? 因为要求的是集合,会有多个众数,如果规定只有一个众数,那么就遍历一次稳稳的了。

最后给出对应的迭代法,其实就是迭代法中序遍历的模板加上递归法中中间节点的处理逻辑。

相关文章:

代码随想录阅读笔记-二叉树【二叉搜索树中的众数】

题目 给定一个有相同值的二叉搜索树&#xff08;BST&#xff09;&#xff0c;找出 BST 中的所有众数&#xff08;出现频率最高的元素&#xff09;。 假定 BST 有如下定义&#xff1a; 结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的…...

AcWing-游戏

1388. 游戏 - AcWing题库 所需知识&#xff1a;博弈论&#xff0c;区间dp 由于双方都采取最优的策略来取数字&#xff0c;所以结果为确定的&#xff0c;有可能会有多个不同的过程&#xff0c;但是我们只需要关注最终结果就行了。 方法一&#xff1a; 定义dp[i][j] 表示区间…...

Mybatis——一对一映射

一对一映射 预置条件 在某网络购物系统中&#xff0c;一个用户只能拥有一个购物车&#xff0c;用户与购物车的关系可以设计为一对一关系 数据库表结构&#xff08;唯一外键关联&#xff09; 创建两个实体类和映射接口 package org.example.demo;import lombok.Data;import …...

Web 安全之 SSL 剥离攻击详解

目录 SSL/TLS简介 SSL 剥离攻击原理 SSL 剥离攻击的影响 SSL 剥离攻击的防范措施 小结 SSL 剥离攻击&#xff08;SSL Stripping Attack&#xff09;是一种针对安全套接层&#xff08;SSL&#xff09;或传输层安全性&#xff08;TLS&#xff09;协议的攻击手段&#xff0c;…...

数据结构——顺序表(C语言)

目录 一、顺序表概念 二、顺序表分类 1.静态顺序表 2.动态顺序表 三、顺序表的实现 1.顺序表的结构体定义 2. 顺序表初始化 3.顺序表销毁 4.顺序表的检验 5.顺序表打印 6.顺序表扩容 7.顺序表尾插与头插 8.尾删与头删 9.在pos处插入数据 10.在pos处删除数据 11.查找数据 …...

利用Idea实现Ajax登录(maven工程)

一、新建一个maven工程&#xff08;不会建的小伙伴可以参考Idea引入maven工程依赖(保姆级)-CSDN博客&#xff09;&#xff0c;工程目录如图 ​​​​​​​ js文件可以上up网盘提取 链接&#xff1a;https://pan.baidu.com/s/1yOFtiZBWGJY64fa2tM9CYg?pwd5555 提取码&…...

环信IM集成教程——Web端UIKit快速集成与消息发送

写在前面&#xff1a; 千呼万唤始出来&#xff0c;环信Web端终于出UIKit了&#xff01;&#x1f389;&#x1f389;&#x1f389; 文档地址&#xff1a;https://doc.easemob.com/uikit/chatuikit/web/chatuikit_overview.html 环信单群聊 UIKit 是基于环信即时通讯云 IM SDK 开…...

Anaconda如何切换国内镜像源

一、anaconda如何切换阿里镜像源 在Anaconda中切换到阿里云镜像源可以通过以下步骤进行&#xff1a; 1、打开终端&#xff08;Windows&#xff09;或者命令行界面&#xff08;macOS/Linux&#xff09;。 2、执行以下命令来配置阿里云镜像源&#xff1a; conda config --add…...

Android 14.0 添加自定义服务,并生成jar给第三方app调用

1.概述 在14.0系统ROM产品定制化开发中,由于需要新增加自定义的功能,所以要增加自定义服务,而app上层通过调用自定义服务,来调用相应的功能,所以系统需要先生成jar,然后生成jar 给上层app调用,接下来就来分析实现的步骤,然后来实现相关的功能 从而来实现所需要的功能 …...

解决沁恒ch592单片机在tmos中使用USB总线时,接入USB Hub无法枚举频繁Reset的问题

开发产品时采用了沁恒ch592&#xff0c;做USB开发时遇到了一个奇葩的无法枚举问题。 典型症状 使用USB线直连电脑时没有问题&#xff0c;可以正常使用。 如果接入某些特定方案的USB Hub&#xff08;例如GL3510、GL3520&#xff09;&#xff0c;可能会出现以下2种情况&#xf…...

nvm保姆级安装使用教程

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 开发环境篇 ✨特色专栏&#xff1a; M…...

大语言模型LLM《提示词工程指南》学习笔记02

文章目录 大语言模型LLM《提示词工程指南》学习笔记02设计提示时需要记住的一些技巧零样本提示少样本提示链式思考&#xff08;CoT&#xff09;提示自我一致性生成知识提示 大语言模型LLM《提示词工程指南》学习笔记02 设计提示时需要记住的一些技巧 指令 您可以使用命令来指…...

【realme x2手机解锁BootLoader(简称BL)】

realme手机解锁常识 https://www.realme.com/cn/support/kw/doc/2031665 realme手机解锁支持型号 https://www.realmebbs.com/post-details/1275426081138028544 realme x2手机解锁实践 参考&#xff1a;https://www.realmebbs.com/post-details/1255473809142591488 1 下载apk…...

攻防世界 wife_wife

在这个 JavaScript 示例中&#xff0c;有两个对象&#xff1a;baseUser 和 user。 baseUser 对象定义如下&#xff1a; baseUser { a: 1 } 这个对象有一个属性 a&#xff0c;其值为 1&#xff0c;没有显式指定原型对象&#xff0c;因此它将默认继承 Object.prototype。 …...

Visual Studio安装下载进度为零已解决

因为在安装pytorch3d0.3.0时遇到问题&#xff0c;提示没有cl.exe&#xff0c;VS的C编译组件&#xff0c;可以添加组件也可以重装VS。查了下2019版比2022问题少&#xff0c;选择了安装2019版&#xff0c;下面是下载安装时遇到的问题记录&#xff0c;关于下载进度为零网上有三类解…...

矩阵空间秩1矩阵小世界图

文章目录 1. 矩阵空间2. 微分方程3. 秩为1的矩阵4. 图 1. 矩阵空间 我们以3X3的矩阵空间 M 为例来说明相关情况。目前矩阵空间M中只关心两类计算&#xff0c;矩阵加法和矩阵数乘。 对称矩阵-子空间-有6个3X3的对称矩阵&#xff0c;所以为6维矩阵空间上三角矩阵-子空间-有6个3…...

《QT实用小工具·十三》FlatUI辅助类之各种炫酷的控件集合

1、概述 源码放在文章末尾 FlatUI辅助类之各种炫酷的控件集合 按钮样式设置。文本框样式设置。进度条样式。滑块条样式。单选框样式。滚动条样式。可自由设置对象的高度宽度大小等。自带默认参数值。 下面是demo演示&#xff1a; 项目部分代码如下所示&#xff1a; #ifnd…...

dm8 备份与恢复

dm8 备份与恢复 基础环境 操作系统&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) 数据库版本&#xff1a;DM Database Server 64 V8 架构&#xff1a;单实例1 设置bak_path路径 --创建备份文件存放目录 su - dmdba mkdir -p /dm8/backup--修改dm.ini 文件…...

Vue项目中引入html页面(vue.js中引入echarts数据大屏html [静态非数据传递!] )

在项目原有vue&#xff08;例如首页&#xff09;基础上引入html页面 1、存放位置 vue3原有public文件夹下 我这边是新建一个static文件夹 专门存放要用到的html文件 复制拖拽过来 index为html的首页 2、更改路径引入到vue中 这里用到的是 iframe 方法 不同于vue的 component…...

ASTM C1186-22 纤维水泥平板

以无石棉类无机矿物纤维、有机合成纤维或纤维素纤维&#xff0c;单独或混合作为增强材料&#xff0c;以普通硅酸盐水泥或水泥中添加硅质、钙质材料代替部分水泥为胶凝材料&#xff0c;经制浆、成型、蒸汽或高压蒸汽养护制成的板材&#xff0c;俗称水泥压力板。 ASTM C1186-22纤…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

python可视化:俄乌战争时间线关键节点与深层原因

俄乌战争时间线可视化分析&#xff1a;关键节点与深层原因 俄乌战争是21世纪欧洲最具影响力的地缘政治冲突之一&#xff0c;自2022年2月爆发以来已持续超过3年。 本文将通过Python可视化工具&#xff0c;系统分析这场战争的时间线、关键节点及其背后的深层原因&#xff0c;全面…...

新版NANO下载烧录过程

一、序言 搭建 Jetson 系列产品烧录系统的环境需要在电脑主机上安装 Ubuntu 系统。此处使用 18.04 LTS。 二、环境搭建 1、安装库 $ sudo apt-get install qemu-user-static$ sudo apt-get install python 搭建环境的过程需要这个应用库来将某些 NVIDIA 软件组件安装到 Je…...

Qt学习及使用_第1部分_认识Qt---Qt开发基本流程

前言 学以致用,通过QT框架的学习,一边实践,一边探索编程的方方面面. 参考书:<Qt 6 C开发指南>(以下称"本书") 标识说明:概念用粗体倾斜.重点内容用(加粗黑体)---重点内容(红字)---重点内容(加粗红字), 本书原话内容用深蓝色标识,比较重要的内容用加粗倾…...