当前位置: 首页 > 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;用…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...