C++力扣题目501--二叉搜索树中的众数

news/2024/2/23 16:05:09/文章来源:https://blog.csdn.net/weixin_47675625/article/details/135573660

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。

如果树中有不止一个众数,可以按 任意顺序 返回。

假定 BST 满足如下定义:

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

示例 1:

输入:root = [1,null,2,2]
输出:[2]

示例 2:

输入:root = [0]
输出:[0]
提示:
  • 树中节点的数目在范围 [1, 104] 内
  • -105 <= Node.val <= 105

 

思路

这道题目呢,递归法我从两个维度来讲。

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

#递归法

#如果不是二叉搜索树

如果不是二叉搜索树,最直观的方法一定是把这个树都遍历了,用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 ;
}

  1. 把统计的出来的出现频率(即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); // 给频率排个序
  1. 取前面高频的元素

此时数组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 ;
}

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

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

这就考察对树的操作了。

在二叉树:搜索树的最小绝对差 (opens new window)中我们就使用了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;}
};

#迭代法

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

二叉树前中后序转迭代,传送门:

  • 二叉树:前中后序迭代法(opens new window)
  • 二叉树:前中后序统一风格的迭代方式(opens new window)

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

代码如下:

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

#总结

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

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

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

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

最后我依然给出对应的迭代法,其实就是迭代法中序遍历的模板加上递归法中中间节点的处理逻辑,分分钟就可以写出来,中间逻辑的代码我都是从递归法中直接粘过来的。

求二叉搜索树中的众数其实是一道简单题,但大家可以发现我写了这么一大篇幅的文章来讲解,主要是为了尽量从各个角度对本题进剖析,帮助大家更快更深入理解二叉树

需要强调的是 leetcode上的耗时统计是非常不准确的,看个大概就行,一样的代码耗时可以差百分之50以上,所以leetcode的耗时统计别太当回事,知道理论上的效率优劣就行了。

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

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

相关文章

【Redis】非关系型数据库之Redis的增删改查

目录 一、Redis的数据类型分类 二、Redis的字符串类型string 三、Redis的列表list 四、Redis的哈希hash 五、Redis的无序集合set 六、Redis的有序集合zset 七、Redis的通用命令 一、Redis的数据类型分类 通常Redis的数据类型有五大基础类型 String&#xff08;字符串&am…

多机TCP通讯之hello world(C++)

文章目录 TCP是什么准备工作CMakeLists.txt服务端代码客户端代码参考 TCP是什么 TCP&#xff08;传输控制协议&#xff09;是一种在计算机网络中广泛使用的协议&#xff0c;它提供了可靠的、面向连接的数据传输服务。TCP 是 OSI 模型中的传输层协议&#xff0c;它确保了数据的…

idea 安装免费Ai工具 codeium

目录 概述 ide安装 使用 chat问答 自动写代码 除此外小功能 概述 这已经是我目前用的最好免费的Ai工具了&#xff0c;当然你要是有钱最好还是用点花钱的&#xff0c;比如copilot&#xff0c;他可以在idea全家桶包括vs&#xff0c;还有c/c的vs上运行&#xff0c;还贼强&am…

安全狗方案入选工信部《2023年工业和信息化领域数据安全典型案例名单》

近日&#xff0c;工业和信息化部网络安全管理局公布了2023年工业和信息化领域数据安全典型案例名单。 安全狗与厦门卫星定位应用股份有限公司、中移 (上海) 信息通信科技有限公司联合申报的智慧交通云数据安全与隐私保障典型案例也成功入选。 厦门服云信息科技有限公司&#…

132基于matlab的采集信号模极大值以及李氏指数计算

基于matlab的采集信号模极大值以及李氏指数计算&#xff0c; 1)计算信号的小波变换。 2)求出模极大曲线。 3)计算其中两个奇异点的Lipschitz指数&#xff0c;程序已调通&#xff0c;可直接运行。 132matlab模极大曲线Lipschitz (xiaohongshu.com)

【计算机网络】第七,八,九章摘要重点

第七章网络管理 1.计算机网络面临的两大威胁&#xff1f; 恶意程序有&#xff1a;计算机病毒&#xff0c;计算机蠕虫&#xff0c;特洛伊木马&#xff0c;逻辑炸弹&#xff0c;后门入侵和流氓软件。 2.安全的计算机网络四个目标&#xff1a; 机密性&#xff0c;端点鉴别&…

PDF.js实现按需分片加载pdf文件

pdf.js实现按需、分片加载pdf文件 1.服务端配置 分片加载的实现是基于 HTTP-RANGE&#xff0c;即服务端的文件接口必须实现了HTTP-RANGE。 服务端文件接口实现HTTP-RANGE&#xff0c;需要服务端添加如下响应头 [{key: "Accept-Ranges",value: "bytes"}…

C++学习笔记——友元、嵌套类、异常

目录 一、友元 一个使用友元的示例代码 输出结果 二、嵌套类 一个使用嵌套类的示例代码 输出结果 三、异常 一个使用异常处理的示例代码 输出结果 四、结论 五、使用它们的注意事项 上一篇文章链接&#xff1a; C中的继承和模板是非常强大和灵活的特性&#xff0c;它…

03.用于LLMs不同的任务-transformer 架构

大多数现代LLMs都依赖于 transformer 架构,这是 2017 年论文 Attention Is All You Need 中介绍的深度神经网络架构。要理解LLMs,我们必须简要回顾一下最初的转换器,它最初是为机器翻译而开发的,将英语文本翻译成德语和法语。变压器架构的简化版本如图 1.4 所示。 图 1.4 …

Redis:原理速成+项目实战——Redis实战9(秒杀优化)

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位大四、研0学生&#xff0c;正在努力准备大四暑假的实习 &#x1f30c;上期文章&#xff1a;Redis&#xff1a;原理速成项目实战——Redis实战8&#xff08;基于Redis的分布式锁及优化&#xff09; &#x1f4da;订阅专栏&…

springboot第49集:【思维导图】多线程,常用类与基础API,集合框架,泛型,数据结构源码...

多线程创建方式一&#xff1a;继承Thread类多线程创建方式二&#xff1a;实现Runnable接口jdk5.0新增两种创建多线程的方式 image.png image.png image.png image.png image.png new Thread(new Runnable() {public void run() {for (int i 1; i < 100; i) {if (i % 2 0) …

20240116使用Firefly的AIO-3399J的预编译的Android10固件确认RT5640声卡信息

20240116使用Firefly的AIO-3399J的预编译的Android10固件确认RT5640声卡信息 2024/1/16 17:55 百度&#xff1a;RK3399 ALC5640 RK3399 RT5640 BING&#xff1a;RK3399 ALC5640 LINE-IN接麦克风不会有声音的。 耳机只有右边有声音&#xff0c;但是偏小&#xff0c;可以通过音量…

在线SM2加签工具

在线SM2加签工具 - BTool在线工具软件&#xff0c;为开发者提供方便。本工具采用了国密局推荐的SM2签名算法&#xff0c;SM2签名算法是一种基于椭圆曲线密码体系的数字签名算法&#xff0c;是中国国家密码管理局制定的国密标准之一。SM2签名算法的安全性基于椭圆曲线离散对数问…

Elasticsearch Windows部署-ELK技术栈

1、下载Elasticsearch、kibana、logstash 本文不介绍ELK相关原理知识&#xff0c;只记录部署操作过程 下载地址Past Releases of Elastic Stack Software | Elastic 选择同一版本&#xff0c;这里选择是当前最新版本8.11.3 解压放在同目录下&#xff0c;方便后续操作与使用 …

【OpenAI】自定义GPTs应用(GPT助手应用)及外部API接口请求

11月10日&#xff0c;OpenAI正式宣布向所有ChatGPT Plus用户开放GPTs功能 简而言之&#xff1a;GPT应用市场(简称GPTs, 全称GPT Store) Ps&#xff1a; 上图为首次进入时的页面&#xff0c;第一部分是自己创建的GPTs应用&#xff0c;下面是公开可以使用的GPTs应用 一、创建GPTs…

HTML5+CSS3+JS小实例:音频可视化

实例:音频可视化 技术栈:HTML+CSS+JS 效果: 源码: 【HTML】 <!DOCTYPE html> <html lang="zh-CN"> <head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><m…

jmeter--4.参数化的方式

目录 1. 用户定义的变量 2. 用户参数 3. 函数助手 3.1 time获取当前时间 3.2 Random随机数 3.3 随机字符串函数 3.4 字符串变更为大写 4. CSV数据文件设置 5. 接口关联--正则和json等提取 1. 用户定义的变量 线程组->添加->配置元件->用户定义的变量 引用方…

HCIA——12题目-1章选择

学习目标&#xff1a; 计算机网络 1.掌握计算机网络的基本概念、基本原理和基本方法。 2.掌握计算机网络的体系结构和典型网络协议&#xff0c;了解典型网络设备的组成和特点&#xff0c;理解典型网络设备的工作原理。 3.能够运用计算机网络的基本概念、基本原理和基本方法进行…

【Linux】进程信号,相关函数的简单实用

文章目录 一、讨论范围二、信号的结构1.信号的本质2.预备知识2.1 如何发送信号2.2 如何查看后台程序 三、改变信号默认触发方式的两个函数1.signal2.sigaction 四、信号集操作函数和相关指令0.sigprocmask1.sigemptyset2.sigaddset3.sigdelset4.sigfillset 总结 一、讨论范围 编…