当前位置: 首页 > 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;确保网络性能稳定和用户体验良好…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...