二叉搜索树中的众数Java解法

news/2024/3/29 18:57:25/文章来源:https://blog.csdn.net/qq_43593534/article/details/129215075

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

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

假定 BST 满足如下定义:

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-mode-in-binary-search-tree
 

例:

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

解析:由题可知,左子树必须小于等于根节点,右子树必须大于等于根节点,如果为众数,必然为相邻节点,若根节点和左儿子相同,那么左儿子的右儿子只能和根节点相同。同理,若根节点和右儿子相同,那么右儿子的左儿子只能和根节点相同。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> answer = new ArrayList<Integer>();  // 列表存实时众数int base=0, count=0, maxCount=0;  // 当前的判断值,当前值的计数,当前众数的计数public int[] findMode(TreeNode root) {dfs(root);  // 遍历搜索树int[] mode = new int[answer.size()];  // 创建答案存储空间for (int i = 0; i< answer.size(); i++){  // 遍历实时答案存储空间mode[i] = answer.get(i);  // 将答案提出}  return mode;  // 返回答案}public void dfs(TreeNode o){  // 搜索函数if (o == null){  // 叶子节点返回return;}dfs(o.left);  // 左子树遍历update(o.val);  // 更新dfs(o.right);  // 右子树遍历}public void update(int x){  // 更新函数if (x == base){  // 与上一个值相等count++;  // 计数加1}else{count = 1;  // 第一次遇到,计数为1base = x;  // 判断值换成当前值}if (count == maxCount){  // 计数等于当前计数最大值answer.add(base);  // 添加到结果列表中}if (count > maxCount){  // 计数大于当前计数最大值maxCount = count;  // 更新计数最大值answer.clear();  // 清除列表中的过去式众数answer.add(base);  // 更新新的众数}}
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_74022.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Web逆向】万方数据平台正文的逆向分析(上篇--加密发送请求)—— 逆向protobuf

【Web逆向】万方数据平台正文的逆向分析&#xff08;上篇--加密发送请求&#xff09;—— 逆向protobuf声明一、了解protobuf协议&#xff1a;二、前期准备&#xff1a;二、目标网站&#xff1a;三、开始分析&#xff1a;我们一句句分析&#xff1a;先for循环部分&#xff1a;后…

【算法】最短路算法

&#x1f600;大家好&#xff0c;我是白晨&#xff0c;一个不是很能熬夜&#x1f62b;&#xff0c;但是也想日更的人✈。如果喜欢这篇文章&#xff0c;点个赞&#x1f44d;&#xff0c;关注一下&#x1f440;白晨吧&#xff01;你的支持就是我最大的动力&#xff01;&#x1f4…

电子技术——输出阶类型

电子技术——输出阶类型 输出阶作为放大器的最后一阶&#xff0c;其必须有较低的阻抗来保证较小的增益损失。作为放大器的最后一阶&#xff0c;输出阶需要处理大信号类型&#xff0c;因此小信号估计模型不适用于输出阶。尽管如此&#xff0c;输出阶的线性也非常重要。实际上&a…

为什么要用线程池?

1.降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。 2.提高响应速度。当任务到达时&#xff0c;任务可以不需要的等到线程创建就能立即执行。 3.提高线程的可管理性。线程是稀缺资源&#xff0c;如果无限制的创建&#xff0c;不仅会消耗系统资源&#…

Python实现贝叶斯优化器(Bayes_opt)优化支持向量机回归模型(SVR算法)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后获取。1.项目背景贝叶斯优化器 (BayesianOptimization) 是一种黑盒子优化器&#xff0c;用来寻找最优参数。贝叶斯优化器是…

AI_News周刊:第三期

CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 2023.02.20—2023.02.25 News 1.OpenAI 现在正在帮助可口可乐改善其营销和运营 2023 年 2 月 21 日——贝恩公司今天宣布与 OpenAI 建立全球服务联盟&#xff0c;OpenAI 是人工智能系统 ChatGPT、DA…

java Spring JdbcTemplate配合mysql实现数据库表数据添加

本文为 java Spring JdbcTemplate 准备工作的续文 如果您还没有大家好JdbcTemplate 的基础环境 可以先查看前文 首先 之前数据库我们已经弄好了 然后 我们在下面创建一个表 我这里叫 user_list 每一个数据库表 要对应一个实体类 这里 我们打开上一文搭建的项目环境 src下创建…

【华为OD机试模拟题】用 C++ 实现 - 英文输入法(2023.Q1)

最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 分积木(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 吃火锅(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - RSA 加密算法(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 构成的正方形数量(2023.Q1) 【华为OD机试模拟…

【原创】java+swing+mysql生肖星座查询系统设计与实现

今天我们来开发一个比较有趣的系统&#xff0c;根据生日查询生肖星座&#xff0c;输入生日&#xff0c;系统根据这个日期自动计算出生肖和星座信息反馈到界面。我们还是使用javaswingmysql去实现这样的一个系统。 功能分析&#xff1a; 生肖星座查询系统&#xff0c;顾名思义…

【CSS】CSS 层叠样式表 ① ( 简介 | CSS 引入方式 - 内联样式 | 内联样式语法 | 内联样式缺点 )

文章目录一、CSS 层叠样式表二、CSS 引入方式 - 内联样式1、内联样式语法2、内联样式缺点3、内联样式代码示例① 核心代码示例② 完整代码示例③ 执行结果一、CSS 层叠样式表 CSS 全称 Cascading Style Sheets , 层叠样式表 ; 作用如下 : 设置 HTML 页面 文本内容 的 字体 , 颜…

【华为OD机试模拟题】用 C++ 实现 - 最少停车数(2023.Q1)

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

绝对让你明明白白,脚把脚带你盯着 I2C 时序图将 I2C 程序给扣出来(基于STM32的模拟I2C)

目录前言一、关于STM32 I/O端口位的基本结构讲解二、模拟I2C编写前的需知道的知识1、I2C简介2、根据时序编写模拟I2C程序重要的两点Ⅰ、主机发送数据给从机时的时序控制Ⅱ、主机接收来自从机的数据时的时序控制Ⅲ、完整的I2C时序图&#xff08;按写程序的思想分割时序&#xff…

2023年湖北住建厅七大员建筑八大员怎么报考?启程别

2023年湖北住建厅七大员建筑八大员怎么报考&#xff1f;启程别 建筑施工企业关键技术岗位人员可以叫七大员也可以叫八大员&#xff0c;施工现场专业人员&#xff0c;从事相关岗位人员都应该持证上岗。 为什么有的叫七大员&#xff1f;有的叫八大员呢&#xff1f;甚至还有五大员…

sklearn学习-朴素贝叶斯(二)

文章目录一、概率类模型的评估指标1、布里尔分数Brier Score对数似然函数Log Loss二、calibration_curve&#xff1a;校准可靠性曲线三、多项式朴素贝叶斯以及其变化四、伯努利朴素贝叶斯五、改进多项式朴素贝叶斯&#xff1a;补集朴素贝叶斯ComplementNB六、文本分类案例TF-ID…

【信管12.5】项目集与项目组合管理

项目集与项目组合管理之前学习的 PMP 相关的项目管理知识&#xff0c;其实都是针对一个项目的管理过程。但是&#xff0c;在一个组织企业中&#xff0c;往往不止一个项目&#xff0c;可能会有多个相关联的项目&#xff0c;这种情况就叫做项目集。另外&#xff0c;多个项目一起完…

二叉树——堆

一&#xff0c;树的概念及结构 1.树 4.结点的度&#xff1a;一个节点含有子树的个数称为该结点的度&#xff1b;如&#xff1a;A 的度为6. 5.叶节点或终端节点&#xff1a;度为0的节点称为叶节点&#xff1b;如&#xff1a;B 6.非终端结点或分支节点&#xff1a;度部位0的结…

MySQL基础知识-刷题笔记

数据库刷题笔记 查漏补缺&#xff0c;面试八股文&#xff0c;以下内容未说明的均以MySQL数据库为准 where 不能和聚合函数一起使用 having可以和聚合函数一起使用 having必须与group by一起使用1、SUBSTRING_INDEX(str ,substr ,n)&#xff1a;返回字符substr在str中第n次出现位…

【强化学习】强化学习数学基础:贝尔曼公式

强化学习数学基础&#xff1a;贝尔曼公式强化学习的数学原理课程总览贝尔曼公式&#xff08;Bellman Equation&#xff09;一个示例状态值贝尔曼公式&#xff1a;推导过程贝尔曼公式&#xff1a;矩阵-向量形式&#xff08;Matrix-vector form&#xff09;贝尔曼公式&#xff1a…

基于合作型Stackerlberg博弈的考虑差别定价和风险管理的微网运行策略研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

从网易到支付宝,3年外包生涯做完,我这人生算是彻底废了......

我为什么一直做外包呢&#xff0c;原因是薪资和技术方面。 在华三做了一年外包&#xff0c;薪资5k&#xff0c;功能测试&#xff0c;接触Linux和网络&#xff0c;但是说实在的技术很难沉淀&#xff0c;就像雾里看花一样&#xff0c;过年之后&#xff0c;想走的人都走了&#x…