【算法与数据结构】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题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析:根据前面几篇文章98、LeetCode验证二叉搜索树、530、LeetCode二叉搜索树的最小绝对差。我们知道二叉搜…...

Spring MVC 六 - DispatcherServlet处理请求过程
前面讲过了DispatcherServlet的初始化过程(源码角度的DispatcherServlet的具体初始化过程还没说,先放一放),今天说一下DispatcherServlet处理请求的过程。 处理过程 WebApplicationContext绑定在当前request属性上(属…...

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

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

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

MySql 笔记
数据结构:BTREE 二叉树:顺序增长依次查询效率低 红黑树: 数据多了深度越深,效率自然低了 HASH: 查询条件限制 B-TREE:度(degree)-节段的数据存储个数,叶节点具有 相…...

部署elasticsearch集群
创建es集群 编写一个docker-compose.yaml文件,内容如下 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密码(现代密码)因数分解因数分解 共享素数Bigrsa 低加密指数攻击(小明文攻击)crypto5 共模攻击rsa_output 广播攻击Crazy_Rsa_Tech 待补充 CTF入门学习笔记——Crypto密码(现代密码…...

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

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

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

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

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

Django创建应用、ORM的进阶使用及模型类数据库迁移
1 Django项目创建第一个应用 Django 项目就是基于 Django 框架开发的 Web 应用,它包含了一组配置和多个应用,我们把应用称之为 App,在前文中对它也做了相应的介绍,比如 auth、admin,它们都属于 APP。 一个 App 就是一…...

tcpdump 如何使用
tcpdump 是一个在Unix和类Unix系统上运行的网络抓包工具,它用于捕获网络流量并将其转储到文件中以供后续分析。tcpdump非常强大,可以用于监控、调试和分析网络通信,用于排查网络问题以及安全审计。以下是关于如何使用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 安全策略限制,在 cross-request 升级到 3.0 后, 不再支持文件上传功能,并且需要通过以下方法查看 network:1.首先在chrome 输入 > chrome://extensions打开扩展页2.开启开发者模式3.点击 cross…...

自动驾驶(apollo)
💓博主csdn个人主页:小小unicorn 🚚代码仓库:小小unicorn的代码仓库🚚 🌹🌹🌹关注我带你学习编程知识 自动驾驶技术 引言自动驾驶的基本原理自动驾驶的技术挑战自动驾驶的潜在影响结…...

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

26. 不相同的字符串(第一期模拟笔试)
题目:样例: 输入 1 abab 输出 2 思路: 这里的题目要求我们要最少操作删除次数,我们可以先统计每个字符个数,然后开始删除,每操作删除一次,就会产生一个新字符,ans r[i] >> 1…...

Rethink LSTMGRU
LSTM 设计思想 姑且不看偏置。 W W W 和 U U U 是加权的矩阵,写模型的时候用 nn.Linear(in_dim, out_dim) 就成; σ \sigma σ 是 Sigmoid 函数 第一条,遗忘门,定义为 有多少内容需要被遗忘;第二条:输入门…...

状态管理艺术——借助Spring StateMachine驭服复杂应用逻辑
文章目录 1. 什么是状态2. 有限状态机概述3. Spring StateMachine4. Spring StateMachine 入门小案例4.1 接口测试 5. 总结 1. 什么是状态 在开发中,无时无刻离不开状态的一个概念,任何一条数据都有属于它的状态。 比如一个电商平台,一个订…...

获取和设置小程序和h5的页面栈
获取页面栈: 语法: let pages getCurrentPages(); 设置页面栈: 小程序语法: pages.data H5语法: pages let pages getCurrentPages(); let page pages[pages.length - 2]; if(page.route "pages/conf…...

Mysql基于成本选择索引
本篇文章介绍mysql基于成本选择索引的行为,解释为什么有时候明明可以走索引,但mysql却没有走索引的原因 mysql索引失效的场景大致有几种 不符合最左前缀原则在索引列上使用函数或隐式类型转换使用like查询,如 %xxx回表代价太大索引列区分度过…...

Element-ui container常见布局
1、header\main布局 <template> <div> <el-container> <el-header>Header</el-header> <el-main>Main</el-main> </el-container> </div> </template> <style> .el-header { …...

ssm实现折线统计图
方法1:单张数据表中的数据图表生成 图表统计,查看部门人数统计这里实现的时单张表中的数据实现部门人数折线统计图展示。 <script type"text/javascript">// 利用AjAx来获取后台传入的数据(Responsebody注解传入的&…...

GLSL ES着色器 精度限定字
目录 前言 WebGL支持的三种精度 数据类型的默认精度 float类型没有默认精度 预处理指令 在GLSL ES中常用的三种预处理指令。 预定义的内置宏 前言 GLSL ES新引入了精度限定字,目的是帮助着色器程序提高运行效率,削减内存开支。顾名思义…...

webrtc的FULL ICE和Lite ICE
1、ICE的模式 分为FULL ICE和Lite ICE: FULL ICE:是双方都要进行连通性检查,完成的走一遍流程。 Lite ICE: 在FULL ICE和Lite ICE互通时,只需要FULL ICE一方进行连通性检查, Lite一方只需回应response消息。这种模式对于部署在公网…...

flink的几种常见的执行模式
背景 在运行flink时,我们经常会有几种不同的执行模式,比如在IDE中启动时,通过提交到YARN上,还有通过Kebernates启动时,本文就来记录一下这几种模式 flink的几种执行模式 flink嵌入式模式: 这是一种我们在…...