【二叉树算法题记录】501. 二叉搜索树中的众数

news/2024/7/25 20:44:28/文章来源:https://blog.csdn.net/weixin_43627638/article/details/139122916

题目链接

题目描述

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

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

假定 BST 满足如下定义:

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

题目分析

首先我们遍历整个树,可以记录每个元素出现的次数(用map),然后对map进行排序,我们就能得到出现频率最高的元素。如下:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:void traversal(TreeNode* cur, vector<int>& vec){if(cur==NULL) return;traversal(cur->left, vec);vec.push_back(cur->val);traversal(cur->right, vec);}bool static cmp_value(const pair<int, int>& left, const pair<int, int>& right){return left.second > right.second;}public:vector<int> findMode(TreeNode* root) {vector<int> result;vector<int> vec;// 遍历二叉树traversal(root, vec);// 利用map记录每个元素出现的次数unordered_map<int, int> map;    for(int i = 0; i < vec.size(); i++){map[vec[i]]++;  // 利用key记录出现的元素,value记录元素出现次数}// 根据value的大小对map进行排序vector<pair<int, int>> vec2(map.begin(), map.end());sort(vec2.begin(), vec2.end(), cmp_value);  // 这里定义了自己的比较方法cmp_value// 找map中value最大的元素result.push_back(vec2[0].first);// 因为众数可能不止一个,所以要看后面是否有key有一样的valuefor(int i = 1; i < vec2.size(); i++){if(vec2[i].second == vec2[0].second) result.push_back(vec2[i].first);else break;}return result;}
};

也可以在递归的同时就用map进行统计,修改后代码如下:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:void traversal(TreeNode* cur, unordered_map<int, int>& map){if(cur==NULL) return;traversal(cur->left, map);map[cur->val]++;traversal(cur->right, map);}bool static cmp_value(const pair<int, int>& left, const pair<int, int>& right){return left.second > right.second;}public:vector<int> findMode(TreeNode* root) {vector<int> result;// 遍历二叉树unordered_map<int, int> map;traversal(root, map);// 根据value的大小对map进行排序vector<pair<int, int>> vec(map.begin(), map.end());sort(vec.begin(), vec.end(), cmp_value);  // 这里定义了自己的比较方法cmp_value// 找map中value最大的元素result.push_back(vec[0].first);// 因为众数可能不止一个,所以要看后面是否有key有一样的valuefor(int i = 1; i < vec.size(); i++){if(vec[i].second == vec[0].second) result.push_back(vec[i].first);else break;}return result;}
};

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

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

相关文章

算法之背包问题

可分的背包问题是可以用贪心法来解决&#xff0c;而0-1背包问题通常使用动态规划方法来解决。 可分背包问题&#xff1a; 在可分背包问题中&#xff0c;物品可以被分割&#xff0c;您可以取走物品的一部分以适应背包的容量。这里的关键是物品的价值密度&#xff0c;即单…

间接平差——以水准网平差为例 (python详细过程版)

目录 一、原理概述二、案例分析三、代码实现四、结果展示本文由CSDN点云侠原创,间接平差——以水准网平差为例 (python详细过程版),爬虫自重。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT生成的文章。 一、原理概述 间接平差的函数模型和随机模型…

py黑帽子学习笔记_scapy

简介 代码简洁&#xff1a;相比于前两个博客总结&#xff0c;很多socket操作&#xff0c;如果使用scapy仅需几行代码即可实现 获取邮箱身份凭证 编写基础嗅探器&#xff0c;脚本可显示任何收到的一个包的详细情况 直接运行 尝试监听邮件收发&#xff0c;监听指定端口&#x…

解密网络流量监控:优化IT运维的利器

引言&#xff1a; 在当今数字化时代&#xff0c;网络流量监控是维护网络稳定与业务连续性的关键。作为一名资深网络工程师&#xff0c;我将分享一些关于网络流量监控的重要知识&#xff0c;并探讨如何在IT运维中运用这一工具优化网络性能&#xff0c;确保业务的顺畅进行。 1. 网…

Biological Psychiatry:内源性功能连接的特定模式与强迫症的伤害回避有关

摘要 强迫症(OCD)患者通常在没有实际威胁的情况下表现出持续的回避行为。强迫症对生活质量的影响和患者之间的异质性使得寻找新的大脑-行为干预目标十分有必要。基于啮齿类动物和非人灵长类动物持续回避行为的机制和解剖学研究&#xff0c;本研究的目标是测试持续回避行为相关…

用于脑肿瘤分割的跨模态深度特征学习| 文献速递-深度学习肿瘤自动分割

Title 题目 Cross-modality deep feature learning for brain tumor segmentation 用于脑肿瘤分割的跨模态深度特征学习 01 文献速递介绍 作为最致命的流行病&#xff0c;脑肿瘤的研究越来越受到关注。本文研究了一种基于深度学习的自动分割胶质瘤的方法&#xff0c;称为脑…

百度ERNIE系列预训练语言模型浅析(4)-总结篇

总结&#xff1a;ERNIE 3.0与ERNIE 2.0比较 &#xff08;1&#xff09;相同点&#xff1a; 采用连续学习 采用了多个语义层级的预训练任务 &#xff08;2&#xff09;不同点&#xff1a; ERNIE 3.0 Transformer-XL Encoder(自回归自编码), ERNIE 2.0 Transformer Encode…

Pandas-中axis的用法

在Pandas中&#xff0c;min(axis)方法是计算DataFrame或Series中每行或每列的最小值的函数。该函数可以接受一个参数axis&#xff0c;用于指定计算最小值的方向。当axis0时&#xff0c;表示沿着行的方向计算最小值&#xff1b;当axis1时&#xff0c;表示沿着列的方向计算最小值…

网络原理-------TCP协议

文章目录 TCP协议TCP协议段格式TCP原理确认应答机制 (安全机制)超时重传机制 (安全机制)连接管理机制 (安全机制)滑动窗口 (效率机制)流量控制 (安全机制)拥塞控制 (安全机制)延迟应答 (效率机制)捎带应答 (效率机制) 基于TCP的应用层协议 TCP协议 TCP, 即 Transmission Contr…

c语言 分而治之(施特拉森矩阵乘法)

给定两个大小分别为 nxn 的方阵 A 和 B&#xff0c;求它们的乘法矩阵。 朴素方法&#xff1a;以下是两个矩阵相乘的简单方法。 void multiply(int A[][N], int B[][N], int C[][N]) { for (int i 0; i < N; i) { for (int j 0; j < N; j) { …

Vanna使用ollama分析本地MySQL数据库

上一章节中已经实现了vanna的本地运行&#xff0c;但是大模型和数据库都还是远程的&#xff0c;因为也就没办法去训练&#xff0c;这节一起来实现vanna分析本地mysql数据库&#xff0c;因为要使用本地大模型&#xff0c;所以开始之前需要给本地安装好大模型&#xff0c;我这里用…

Redis面试题深度解析

1、我看你做的项目中&#xff0c;都用到了redis&#xff0c;你在最近的项目中哪些场景使用了redis呢? 2、缓存穿透 布隆过滤器的误判现象 Redisson和Guava都对布隆过滤器进行了实现 3、缓存击穿 互斥锁&#xff0c;就是一个线程来修改&#xff0c;并占据了锁&#xff0c;另外其…

基于 Coze 从 0-1 搭建专属 小白的Bot 机器人

基于 Coze 从 0-1 搭建专属 小白的Bot 机器人 ​ 作为一个GIS从业人员&#xff0c;对于AI的使用是必不可少的&#xff0c;在过去的一两年里各种大模型频出&#xff0c;AI技术已经成为GIS领域的一项重要工具&#xff0c;为我们提供了许多强大的功能和解决方案。看到好文章都在介…

AI视频教程下载:全面掌握ChatGPT和LangChain开发AI应用(附源代码)

这是一门深入的课程&#xff0c;涉及ChatGPT、LangChain和Python。打造专注于现实世界AI集成的AI应用&#xff0c;课件附有每一节涉及到的源代码。 **你将学到什么&#xff1a;** - 将ChatGPT集成到LangChain的生产风格应用中 - 使用LangChain组件构建复杂的文本生成管道 - …

Jeecg | 完成配置后,如何启动整个项目?

前端启动步骤&#xff1a; 1. 以管理员身份打开控制台&#xff0c;切换到前端项目目录。 2. 输入 pnpm install 3. 输入 pnpm dev 4. 等待前端成功运行。 可以看到此时前端已经成功启动。 后端启动步骤&#xff1a; 1. 启动 mysql 服务器。 管理员身份打开控制台&#…

Nginx网页服务

nginx的配置: 1、全局块&#xff1a;全局配置&#xff0c;对全局生效&#xff1b; 2、events块&#xff1a;配置影响 Nginx 服务器与用户的网络连接&#xff1b; 3、http块&#xff1a;配置代理&#xff0c;缓存&#xff0c;日志定义等绝大多数功能和第三方模块的配置&#xf…

JavaDS-学习数据结构之如果从零开始手搓顺序表,顺带学习自定义异常怎么用!

前言 笔者开始学习数据结构了,虽然笔者已经会用了,不管是C 中的stl亦或是Java 中的集合,为了算法比赛多少都突击过,但只知其然而不知其所以然,还是会限制发展的,因此,笔者写下这篇博客.内容是手搓一个顺序表.顺带加一点异常的使用,大伙看个乐子就好了.有错误直接私信喷我就好了…

HarmonyOS-9(stage模式)

配置文件 {"module": {"requestPermissions": [ //权限{"name": "ohos.permission.EXECUTE_INSIGHT_INTENT"}],"name": "entry", //模块的名称"type": "entry", //模块类型 :ability类型和…

Sourcetree安装教程及使用

1 Sourcetree介绍 Sourcetree是一款免费的Git图形化客户端&#xff0c;它由Atlassian开发&#xff0c;提供了跨平台的支持&#xff0c;可运行在Windows和Mac操作系统上。Sourcetree可以让开发者更方便地使用Git来管理代码&#xff0c;不需要在命令行中输入复杂的Git命令&#x…

什么是数字化采购?一文解析!

在快速发展的数字经济时代&#xff0c;越来越多的企业开始想要了解什么是数字化采购&#xff1f;因为数字化采购已经成为提升效率、降低成本的关键举措。简单来说&#xff0c;采购数字化就是利用先进的数字化技术和工具&#xff0c;对传统的采购流程进行改造和优化&#xff0c;…