二叉搜索树的众数(力扣501)

devtools/2025/1/15 22:10:04/

题目如下:

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

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

假定 BST 满足如下定义:

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

示例 1:

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

示例 2:

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

提示:

  • 树中节点的数目在范围 [1, 104] 内
  • -105 <= Node.val <= 105

解题思路如下:直接暴力的算法就是遍历一遍树然后用map记录,最后再对map里的频率进行排序。但是这颗树是二叉搜索树,所以我们要利用好特性,在中序遍历的同时,设置变了count和maxTime来记录下出现的次数,其中当count大于maxTime时就可以动态改变最大值,而当相等时就把该数弹进容器里

代码实现如下:

class Solution {

public:

     int count=0;int maxSize=0;TreeNode*pre=nullptr;vector<int>result;

     void  travel(TreeNode*cur){

        if(cur==nullptr)return;

        travel(cur->left);

        if(pre==nullptr){count=1;}//是空的话说明cur遍历到叶子了

        else if(pre->val==cur->val){count++;}

        else {count=1;}

        pre=cur;//第一次

        if(count==maxSize){

            result.push_back(cur->val);

        }

        if(count>maxSize){

            maxSize=count;

            result.clear();

            result.push_back(cur->val);

        }travel(cur->right);

     }

     

    vector<int> findMode(TreeNode* root) {

      travel(root);

      return result;

    }

};


http://www.ppmy.cn/devtools/19974.html

相关文章

[阅读笔记16][Orca-2]Teaching Small Language Models How to Reason

接下来是Orca-2&#xff0c;这篇是微软在23年11月发表的论文&#xff0c;在Orca-1的基础上又进行了一些改进。 作者希望教会Orca-2各种推理策略&#xff0c;例如逐步思考、回忆然后回答、先回忆再推理再回答、直接生成回答等等策略。并且Orca-2应该能针对不同任务应该使用最合适…

机器学习学习 - 数据预处理

机器学习学习笔记 - 数据预处理 数据预处理是机器学习项目中不可或缺的一环&#xff0c;它涉及到数据的清洗、格式化、归一化、特征提取等一系列操作&#xff0c;以便为后续的模型训练和分析提供高质量的数据集。以下是关于数据预处理的一些关键步骤和注意事项。 一、数据准备…

Redis入门到通关之数据结构解析-Dict

文章目录 概述构成Dict的扩容Dict的rehash总结 欢迎来到 请回答1024 的博客 &#x1f353;&#x1f353;&#x1f353;欢迎来到 请回答1024的博客 关于博主&#xff1a; 我是 请回答1024&#xff0c;一个追求数学与计算的边界、时间与空间的平衡&#xff0c;0与1的延伸的后端开…

制造型企业 如何实现便捷的机台文件统一管理?

机台文件统一管理&#xff0c;这是生产制造型企业都需要去做的&#xff0c;机台文件需要统一管理的原因主要包括以下几点&#xff1a; 1、提高效率&#xff1a;统一管理可以简化文件的访问和使用过程&#xff0c;提高工作效率&#xff0c;尤其是在需要频繁访问或更新机台文件的…

【保姆级教程】Windows 远程登录 Ubuntu桌面环境

前言 在Windows下远程访问Linux服务器的桌面&#xff0c;有几种常见的方法&#xff1a; xrdp&#xff08;X Remote Desktop Protocol&#xff09;&#xff1a;xrdp允许Windows使用RDP&#xff08;Remote Desktop Protocol&#xff09;来连接到Linux服务器的桌面。这种方式相对…

深入理解Java消息中间件-组件-消费者和生产者

引言&#xff1a; 在软件开发中&#xff0c;消息的消费者和生产者是实现异步通信的重要组成部分&#xff0c;它们通过消息队列中间件实现了解耦和并发处理。本文将详细介绍消息的消费者和生产者的实现原理以及其背后的工作原理。 一、实现原理 消息的消费者和生产者的实现依赖…

如何防止黑客恶意的刷端口

我们可以在把这个端口作为Redis的一个key&#xff0c;&#xff08;Redis是kv结构的&#xff0c;v具有类型结构&#xff09;我们可以约定1秒钟超过多少次就算攻击&#xff08;比如1秒钟十次&#xff09;&#xff0c;当一秒钟刷新超过十次我们就认为是在刷新我们的接口&#xff0…

ZYNQ--PL读写PS端DDR数据

PL 和PS的高效交互是zynq 7000 soc开发的重中之重,我们常常需要将PL端的大量数 据实时送到PS端处理,或者将PS端处理结果实时送到PL端处理,常规我们会想到使用DMA 的方式来进行,但是各种协议非常麻烦,灵活性也比较差,本节课程讲解如何直接通过AXI总 线来读写PS端ddr的数据…