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

算法力扣刷题记录 五十六【501.二叉搜索树中的众数】

前言

二叉搜索树操作,继续。
记录 五十六【501.二叉搜索树中的众数】


一、题目阅读

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

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

假定 BST 满足如下定义:

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

示例 1:
在这里插入图片描述

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

示例 2:

输入:root = [0]
输出:[0]

提示:

树中节点的数目在范围 [1, 10^4] 内
-10^5 <= Node.val <= 10^5

进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)


二、尝试实现

依然使用二叉搜索树中序遍历得到有序递增序列的特性。

思路【直白想法】

  1. 借助数组,通过中序遍历将二叉搜索树中的值取出来。再在数组中操作。
  2. 在数组中使用双指针循环,判断一个值出现的次数,再和最大次数记录比较:
  • 如果比最大出现次数的记录小,那么不操作;
  • 如果相等,那么加入到返回值数组中;
  • 如果比最大出现次数的记录大,判断返回值数组中是否为空,先清空后加入。

代码实现【借助数组,额外开辟空间】

/*** 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 {
public:void traversal(TreeNode* cur,vector<int>& nums){if(!cur) return;traversal(cur->left,nums);nums.push_back(cur->val);traversal(cur->right,nums);return;}vector<int> findMode(TreeNode* root) {vector<int> result;vector<int> nums;traversal(root,nums);int max = 0;for(int i = 0;i < nums.size();){int j=i+1;int count = 1;for(;j < nums.size();j++){if(nums[j] == nums[i]){count++;}else{break;}}if(count > max){if(!result.empty()) result.clear();result.push_back(nums[i]);max = count;}else if(count == max){result.push_back(nums[i]);}i = j;}return result;}
};

三、参考学习

参考学习链接

学习目标:如何在树中边遍历边确定众数?肯定还是双指针。尝试一下:有bug

class Solution {
public:int maxcount = 0;//记录最大次数int count = 1;//计数。TreeNode* pre =  nullptr;void traversal(TreeNode* cur,vector<int>& nums){if(!cur) return;traversal(cur->left,nums);if(pre && pre->val == cur->val){count++;}else if(pre && pre->val != cur->val){if(count > maxcount){if(!nums.empty()) nums.clear();nums.push_back(pre->val);maxcount = count;//最大值更新}else if(count == maxcount){nums.push_back(pre->val);}count = 1;//重新计数新的值pre = cur;//此处才更新pre}else if(!pre){pre = cur;//初始时,避免pre空}traversal(cur->right,nums);return;}vector<int> findMode(TreeNode* root) {vector<int> result;traversal(root,result);//处理最后}
};

使用时候,如何结束时也能操作元素呢?在cur->right后还有处理逻辑。

学习内容

  1. 双指针法解决:先说误区
  • 从借助数组的代码实现中发现遍历数组时,使用了i,j相当于i不动,j移动,统计这个元素出现次数。如果nums[j] != nums[i]说明nums[i]出现次数统计完毕。接下来比较count和max。
  • 没有想到可以相邻元素比较,如果相等,count++。count加一次,和max比较一次;不相等时,前面的count已经放到结果里。每一次都要进行count和max比较。
  • 尝试双指针错误在于,认为pre->val和cur->val不相等时,才更新pre,才比较count和max。正确:pre紧跟cur,把count和max的比较放到if外面,这样count更新,max更新。
  • 总结:错误——元素比较不相等时,统计完一个元素次数后放入结果;正确——每次元素比较,即使相等,也要判断count和max。
  1. 双指针代码修正
class Solution {
public:int maxcount = 0;//记录最大次数int count = 1;//计数。TreeNode* pre =  nullptr;void traversal(TreeNode* cur,vector<int>& nums){if(!cur) return;traversal(cur->left,nums);if(pre && pre->val == cur->val){count++;}else if(pre && pre->val != cur->val ){count = 1;//重新计数新的值}pre = cur;//初始时,避免pre空if(count > maxcount){if(!nums.empty()) nums.clear();nums.push_back(pre->val);maxcount = count;//最大值更新}else if(count == maxcount){nums.push_back(pre->val);}traversal(cur->right,nums);return;}vector<int> findMode(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};
  1. 迭代法:中序迭代模版,加中间节点处理逻辑。
  2. 普通二叉树如何求众数?
  • 普通二叉树数值没有任何关系,那么双指针法不成立。不过借助数组方法依然可以用。
  • 借助数组:遍历取出所有值放到vector里面,之后sort从小到大排个序,遍历数组;
  • 参考借助数组思路:用unordered_map统计元素出现次数,再把map转换成vector,再自定义比较函数,带入sort中,得到从大到小的排序vector。
  1. 普通二叉树求众数代码实现:
/*** 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 {
public:void traversal(TreeNode* cur,unordered_map<int,int>& nums){if(!cur) return;nums[cur->val]++;traversal(cur->left);traversal(cur->right);}bool cmp(const pair<int,int>& a,const pair<int,int>& b) const{return a.second > b.second;}vector<int> findMode(TreeNode* root) {vector<int> result;unordered_map<int,int> map;traversal(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 = 0;i <vec.size();i++){if(vec[i].second == vec[0].second) result.push_back(vec[i].first);}return result;}
};

总结

【501.二叉搜索树中的众数】和【求普通二叉树的众数】
在这里插入图片描述
(欢迎指正,转载标明出处)

相关文章:

算法力扣刷题记录 五十六【501.二叉搜索树中的众数】

前言 二叉搜索树操作&#xff0c;继续。 记录 五十六【501.二叉搜索树中的众数】 一、题目阅读 给你一个含重复值的二叉搜索树&#xff08;BST&#xff09;的根节点 root &#xff0c;找出并返回 BST 中的所有 众数&#xff08;即&#xff0c;出现频率最高的元素&#xff09;…...

分布式搜索引擎ES-Elasticsearch进阶

1.head与postman基于索引的操作 引入概念&#xff1a; 集群健康&#xff1a; green 所有的主分片和副本分片都正常运行。你的集群是100%可用 yellow 所有的主分片都正常运行&#xff0c;但不是所有的副本分片都正常运行。 red 有主分片没能正常运行。 查询es集群健康状态&…...

低代码与传统编程:快速高质量构建系统的比较与方法

在信息技术飞速发展的今天&#xff0c;企业对软件系统的需求不断增加。然而&#xff0c;如何在保证高质量的前提下快速构建系统成为了一个关键问题。本文将深入探讨低代码&#xff08;Low-Code&#xff09;开发与传统代码编程的区别&#xff0c;并探讨如何利用这两种方法快速高…...

WebRTC音视频-环境搭建

目录 期望效果 1:虚拟机和系统安装 2:WebRTC客户端环境搭建 2.1&#xff1a;VScode安装 2.2&#xff1a;MobaXterm安装 3:WebRTC服务器环境搭建 3.1&#xff1a;安装openssh服务器 3.2&#xff1a;安装Node.js 3.3&#xff1a;coturn穿透和转发服务器 3.3.1&a…...

Memcached开发(八):使用PHP进行操作

目录 1. 安装与配置 1.1 安装Memcached服务器 1.2 安装PHP的Memcached扩展 2. 基本操作 2.1 连接Memcached服务器 2.2 设置与获取数据 2.3 删除数据 2.4 检查数据是否存在 2.5 添加和替换数据 3. 高级操作 3.1 批量操作 3.2 数据计数器 3.3 CAS&#xff08;Check …...

[Spring Boot]Protobuf解析MQTT消息体

简述 本文主要针对在MQTT场景下&#xff0c;使用Protobuf协议解析MQTT的消息体 Protobuf下载 官方下载 https://github.com/protocolbuffers/protobuf/releases网盘下载 链接&#xff1a;https://pan.baidu.com/s/1Uz7CZuOSwa8VCDl-6r2xzw?pwdanan 提取码&#xff1a;an…...

什么是Mappers?Mappers的作用是什么?

在软件开发中&#xff0c;“mappers” 通常指的是数据映射器&#xff08;Data Mappers&#xff09;&#xff0c;它们的主要作用是在应用程序的数据持久化层&#xff08;通常是数据库或其他持久化存储&#xff09;与应用程序的业务逻辑之间建立一个映射层。 具体来说&#xff0…...

python-多任务编程

2. 多任务编程 2.1 多任务概述 多任务 即操作系统中可以同时运行多个任务。比如我们可以同时挂着qq&#xff0c;听音乐&#xff0c;同时上网浏览网页。这是我们看得到的任务&#xff0c;在系统中还有很多系统任务在执行,现在的操作系统基本都是多任务操作系统&#xff0c;具备…...

IDEA创建Java工程、Maven安装与建立工程、Web工程、Tomcat配置

《IDEA破解、配置、使用技巧与实战教程》系列文章目录 第一章 IDEA破解与HelloWorld的实战编写 第二章 IDEA的详细设置 第三章 IDEA的工程与模块管理 第四章 IDEA的常见代码模板的使用 第五章 IDEA中常用的快捷键 第六章 IDEA的断点调试&#xff08;Debug&#xff09; 第七章 …...

使用工作流产生高质量翻译内容的实战教程

大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…...

笔记:Few-Shot Learning小样本分类问题 + 孪生网络 + 预训练与微调

内容摘自王老师的B站视频&#xff0c;大家还是尽量去看视频&#xff0c;老师讲的特别好&#xff0c;不到一小时的时间就缕清了小样本学习的基础知识点~Few-Shot Learning (1/3): 基本概念_哔哩哔哩_bilibili Few-Shot Learning&#xff08;小样本分类&#xff09; 假设现在每类…...

初学Mybatis之 CRUD 增删改查

namespace 中的包名要和 Dao/Mapper 接口的包名一致 select&#xff1a;选择&#xff0c;查询语句 同理&#xff0c;还有 insert、update、delete 标签 id&#xff1a;对应的 namespace 中的方法名 resultType&#xff1a;sql 语句执行的返回值 parameterType&#xff1a;…...

Kali Linux APT 设置指南:如何控制软件包更新行为

在我浏览 CSDN 的问答社区时&#xff0c;我发现一篇求助内容是一位用户对于如何在使用 APT 更新时避免更新 Arduino 这个问题感到困惑。这激发了我写这篇博客的灵感。我希望通过这篇文章&#xff0c;帮助那些在 Kali Linux 上使用 APT 管理软件包更新的朋友们&#xff0c;特别是…...

Android 10.0 Settings 加载流程

一、系统设置首页 代码路径&#xff1a;packages/app/Settings/ 1 主界面加载&#xff1a; <!-- Alias for launcher activity only, as this belongs to each profile. --><activity-alias android:name"Settings"android:label"string/settings_la…...

mysql的索引、事务和存储引擎

目录 索引 索引的概念 索引的作用 作用 索引的副作用 创建索引 创建索引的原则和依据 索引的类型 创建索引 查看索引 删除索引 drop 主键索引 普通索引 添加普通索引 唯一索引 添加唯一索引 组合索引 添加组合索引 查询组合索引 全文索引 添加全文索引 …...

基于trace_id实现SpringCloudGateway网关的链路追踪

之前写的两篇关于基于 trace_id 的链路追踪的文章&#xff1a; 基于trace_id的链路追踪&#xff08;含Feign、Hystrix、线程池等场景&#xff09;基于trace_id的链路追踪&#xff08;ForkJoinPool场景&#xff09; 一、引言 在之前的文章中&#xff0c;我们讨论了基于 trace…...

Windows 11 version 22H2 中文版、英文版 (x64、ARM64) 下载 (updated Jul 2024)

Windows 11 version 22H2 中文版、英文版 (x64、ARM64) 下载 (updated Jul 2024) Windows 11, version 22H2&#xff0c;企业版 arm64 x64 请访问原文链接&#xff1a;https://sysin.org/blog/windows-11/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者…...

【C语言】动态内存管理(上)

文章目录 前言1.为什么要存在动态内存2. malloc和free2.1 malloc2.2 free2.3 使用实例&#xff08;malloc和free&#xff09; 3. calloc3.1 calloc例子 前言 本文开始将开始学习C语言中一个比较重要的知识点或者是操作——动态内存管理。由于本次的知识比较重要&#xff0c;为…...

【BUG】已解决:ModuleNotFoundError: No module named‘ pip‘

已解决&#xff1a;ModuleNotFoundError: No module named‘ pip‘ 目录 已解决&#xff1a;ModuleNotFoundError: No module named‘ pip‘ 【常见模块错误】 【解决方案】 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#xff0c;我是博主英杰…...

网络安全-网络安全及其防护措施11

51.网络容量规划 网络容量规划的概念和重要性 网络容量规划&#xff1a; 是指根据业务需求和预期增长&#xff0c;合理规划和设计网络的带宽、设备和资源&#xff0c;以满足未来网络流量和服务质量的需求。通过有效的网络容量规划&#xff0c;确保网络性能稳定和用户体验良好…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

C#最佳实践:为何优先使用as或is而非强制转换

C#最佳实践&#xff1a;为何优先使用as或is而非强制转换 在 C# 的编程世界里&#xff0c;类型转换是我们经常会遇到的操作。就像在现实生活中&#xff0c;我们可能需要把不同形状的物品重新整理归类一样&#xff0c;在代码里&#xff0c;我们也常常需要将一个数据类型转换为另…...

Docker环境下安装 Elasticsearch + IK 分词器 + Pinyin插件 + Kibana(适配7.10.1)

做RAG自己打算使用esmilvus自己开发一个&#xff0c;安装时好像网上没有比较新的安装方法&#xff0c;然后找了个旧的方法对应试试&#xff1a; &#x1f680; 本文将手把手教你在 Docker 环境中部署 Elasticsearch 7.10.1 IK分词器 拼音插件 Kibana&#xff0c;适配中文搜索…...