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

【算法与数据结构】501、LeetCode二叉搜索树中的众数

文章目录

  • 一、题目
  • 二、解法
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

  思路分析:根据前面几篇文章98、LeetCode验证二叉搜索树、530、LeetCode二叉搜索树的最小绝对差。我们知道二叉搜索树中序遍历时有序数组,那么程序当中去使用pre和cur指针,去判断两个节点键值是否相同,相同则频率++,不同则count记为1,然后判断count是否等于maxcount,如果相等说明是众数,加入结果数组,如果小于,则更新maxcount,并且要清空结果数组(结果数组里面可能有之前maxcount的对应元素),在将更新后的众数加入结果数组,最后不断递归
  程序如下

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;TreeNode* pre = NULL; // 记录前一个节点result.clear();searchBST(root);return result;}
};

三、完整代码

# include <iostream>
# include <vector>
# include <string>
# include <queue>
using namespace std;// 树节点定义
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: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;TreeNode* pre = NULL; // 记录前一个节点result.clear();searchBST(root);return result;}
};// 前序遍历迭代法创建二叉树,每次迭代将容器首元素弹出(弹出代码还可以再优化)
void Tree_Generator(vector<string>& t, TreeNode*& node) {if (!t.size() || t[0] == "NULL") return;    // 退出条件else {node = new TreeNode(stoi(t[0].c_str()));    // 中if (t.size()) {t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->left);              // 左}if (t.size()) {t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->right);             // 右}}
}template<typename T>
void my_print(T& v, const string msg)
{cout << msg << endl;for (class T::iterator it = v.begin(); it != v.end(); it++) {cout << *it << ' ';}cout << endl;
}template<class T1, class T2>
void my_print2(T1& v, const string str) {cout << str << endl;for (class T1::iterator vit = v.begin(); vit < v.end(); ++vit) {for (class T2::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {cout << *it << ' ';}cout << endl;}
}// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();  // size必须固定, que.size()是不断变化的vector<int> vec;for (int i = 0; i < size; ++i) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;
}int main()
{vector<string> t = { "1", "NULL", "2", "2", "NULL", "NULL", "NULL" };   // 前序遍历my_print(t, "目标树");TreeNode* root = new TreeNode();Tree_Generator(t, root);vector<vector<int>> tree = levelOrder(root);my_print2<vector<vector<int>>, vector<int>>(tree, "目标树:");Solution s;vector<int> result = s.findMode(root);my_print(result, "众数:");system("pause");return 0;
}

end

相关文章:

【算法与数据结构】501、LeetCode二叉搜索树中的众数

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析&#xff1a;根据前面几篇文章98、LeetCode验证二叉搜索树、530、LeetCode二叉搜索树的最小绝对差。我们知道二叉搜…...

Spring MVC 六 - DispatcherServlet处理请求过程

前面讲过了DispatcherServlet的初始化过程&#xff08;源码角度的DispatcherServlet的具体初始化过程还没说&#xff0c;先放一放&#xff09;&#xff0c;今天说一下DispatcherServlet处理请求的过程。 处理过程 WebApplicationContext绑定在当前request属性上&#xff08;属…...

Python实现猎人猎物优化算法(HPO)优化BP神经网络回归模型(BP神经网络回归算法)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后获取。 1.项目背景 猎人猎物优化搜索算法(Hunter–prey optimizer, HPO)是由Naruei& Keynia于2022年提出的一种最新的…...

【图论】SPFA求负环

算法提高课笔记 文章目录 基础知识例题虫洞题意思路代码 观光奶牛题意思路代码 单词环题意思路代码 基础知识 负环&#xff1a;环上权值之和是负数 求负环的常用方法 基于SPFA 统计每个点入队次数&#xff0c;如果某个点入队n次&#xff0c;则说明存在负环&#xff08;完全…...

vue3中的吸顶导航交互实现 | VueUse插件

目的&#xff1a;浏览器上下滚动时&#xff0c;若距离顶部的滚动距离大于78px&#xff0c;吸顶导航显示&#xff0c;小于78px隐藏。使用vueuse插件中的useScroll方法​​​​​​​和动态类名控制进行实现 1. 安装 npm i vueuse/core 2. 获得滚动距离 项目中导入&#xff0…...

MySql 笔记

数据结构&#xff1a;BTREE 二叉树&#xff1a;顺序增长依次查询效率低 红黑树&#xff1a; 数据多了深度越深&#xff0c;效率自然低了 HASH&#xff1a; 查询条件限制 B-TREE&#xff1a;度&#xff08;degree&#xff09;-节段的数据存储个数&#xff0c;叶节点具有 相…...

部署elasticsearch集群

创建es集群 编写一个docker-compose.yaml文件&#xff0c;内容如下 version: 2.2 services:es01:image: elasticsearch:7.12.1container_name: es01environment:- node.namees01- cluster.namees-docker-cluster- discovery.seed_hostses02,es03- cluster.initial_master_nod…...

CTF入门学习笔记——Crypto密码(现代密码)

文章目录 CTF入门学习笔记——Crypto密码&#xff08;现代密码&#xff09;因数分解因数分解 共享素数Bigrsa 低加密指数攻击&#xff08;小明文攻击&#xff09;crypto5 共模攻击rsa_output 广播攻击Crazy_Rsa_Tech 待补充 CTF入门学习笔记——Crypto密码&#xff08;现代密码…...

(3)MyBatis-Plus待开发

常用注解 TableName MyBatis-Plus在确定操作的表时&#xff0c;由BaseMapper的泛型决定即实体类型决定&#xff0c;且默认操作的表名和实体类型的类名一致,如果不一致则会因找不到表报异常 //向表中插入一条数据 Test public void testInsert(){User user new User(null, &…...

正则表达式参考手册

修饰符 修饰符用于执行区分大小写和全局匹配: 修饰符描述i执行对大小写不敏感的匹配。g执行全局匹配&#xff08;查找所有匹配而非在找到第一个匹配后停止&#xff09;。m执行多行匹配。 方括号 方括号用于查找某个范围内的字符&#xff1a; 表达式描述[abc]查找方括号之间…...

【农业生产模拟】WOFOST模型与PCSE模型实践

查看原文>>>【农业生产模拟】WOFOST模型与PCSE模型实践 实现作物产量的准确估算对于农田生态系统响应全球变化、可持续发展、科学粮食政策制定、粮食安全维护都至关重要。传统的经验模型、光能利用率模型等估产模型原理简单&#xff0c;数据容易获取&#xff0c;但是…...

PHP8中获取并删除数组中最后一个元素-PHP8知识详解

在php8中&#xff0c;array_pop()函数将返回数组的最后一个元素&#xff0c;并且将该元素从数组中删除。语法格式如下&#xff1a; array_pop(目标数组) 获取并删除数组中最后一个元素&#xff0c;参考代码&#xff1a; <?php $stu array(s001>明明,s002>亮亮,s…...

JS原理-笔记(1/3)

JS原理-笔记&#xff08;1/3&#xff09; 知识点自测 今天课程中涉及到的已学习知识点 函数的call方法-文档链接 // 以指定的this调用函数&#xff0c;并通过 从第二个参数开始依次传递参数 function func(food,drink){console.log(this)console.log(food)console.log(drink)…...

Django创建应用、ORM的进阶使用及模型类数据库迁移

1 Django项目创建第一个应用 Django 项目就是基于 Django 框架开发的 Web 应用&#xff0c;它包含了一组配置和多个应用&#xff0c;我们把应用称之为 App&#xff0c;在前文中对它也做了相应的介绍&#xff0c;比如 auth、admin&#xff0c;它们都属于 APP。 一个 App 就是一…...

tcpdump 如何使用

tcpdump 是一个在Unix和类Unix系统上运行的网络抓包工具&#xff0c;它用于捕获网络流量并将其转储到文件中以供后续分析。tcpdump非常强大&#xff0c;可以用于监控、调试和分析网络通信&#xff0c;用于排查网络问题以及安全审计。以下是关于如何使用tcpdump的详细介绍&#…...

goweb入门

创建gomod项目 go mod init web01新建main.go package mainimport ("fmt""net/http" )func handler(writer http.ResponseWriter, request *http.Request) {fmt.Fprintf(writer, "Hello World,%s!", request.URL.Path[1:]) } func main() {fmt…...

【python爬虫】批量识别pdf中的英文,自动翻译成中文下

不管是上学还是上班,有时不可避免需要看英文文章,特别是在写毕业论文的时候。比较头疼的是把专业性很强的英文pdf文章翻译成中文。我记得我上学的时候,是一段一段复制,或者碰到不认识的单词就百度翻译一下,非常耗费时间。之前的文章提供了批量识别pdf中英文的方法,详见【…...

YApi 新版如何查看 http 请求数据

YApi 新版如何查看 http 请求数据 因chrome 安全策略限制&#xff0c;在 cross-request 升级到 3.0 后&#xff0c; 不再支持文件上传功能&#xff0c;并且需要通过以下方法查看 network:1.首先在chrome 输入 > chrome://extensions打开扩展页2.开启开发者模式3.点击 cross…...

自动驾驶(apollo)

&#x1f493;博主csdn个人主页&#xff1a;小小unicorn &#x1f69a;代码仓库&#xff1a;小小unicorn的代码仓库&#x1f69a; &#x1f339;&#x1f339;&#x1f339;关注我带你学习编程知识 自动驾驶技术 引言自动驾驶的基本原理自动驾驶的技术挑战自动驾驶的潜在影响结…...

web3.0涉及的技术

非同质化代币 非同质化代币&#xff08;Non-Fungible Tokens&#xff0c;NFTs&#xff09;是一种数字资产&#xff0c;与传统的加密货币&#xff08;如比特币或以太币&#xff09;不同&#xff0c;它们具有独特性和不可替代性。NFTs 是基于区块链技术的数字资产&#xff0c;用…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...