【力扣题解】P501-二叉搜索树中的众数-Java题解

👨💻博客主页:@花无缺
欢迎 点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创收录于专栏 【力扣题解】
文章目录
- 【力扣题解】P501-二叉搜索树中的众数-Java题解
- 🌏题目描述
- 💡题解
- 🌏总结
【力扣题解】P501-二叉搜索树中的众数-Java题解
P501-二叉搜索树中的众数
🌏题目描述
给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1:

输入:root = [1,null,2,2]
输出:[2]
示例 2:
输入:root = [0]
输出:[0]
提示:
- 树中节点的数目在范围
[1, 104]内 -105 <= Node.val <= 105
💡题解
递归:
// 节点值的最大出现频率
int maxCount = Integer.MIN_VALUE;
// 统计频率
int count = 0;
List<Integer> res = new LinkedList<>();
// 保存上一个遍历的节点
TreeNode pre = null;
public int[] findMode(TreeNode root) {dfs(root);int[] a = new int[res.size()];for (int i = 0; i < a.length; i++) {a[i] = res.get(i);}return a;
}
public void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);// 当前节点是第一个节点, count 为 1if (pre == null) {count = 1;// 当前节点和前一个节点值相同, count++} else if (pre.val == root.val) {count++;// 当前节点和前一个节点不同, count 变为 1} else {count = 1;}// 更新 pre 节点pre = root;// 如果当前统计到的节点值次数和最大节点值次数相同// 就放入列表 resif (count == maxCount) {res.add(root.val);}// 如果 count > maxCount, 那么就更新 maxCount// 然后先清空 res, 再将当前节点值加入列表 resif (count > maxCount) {maxCount = count;res.clear();res.add(root.val);}dfs(root.right);
}
迭代:
public int[] findMode(TreeNode root) {Deque<TreeNode> stack = new LinkedList<>();TreeNode cur = root;TreeNode pre = null;// 节点值的最大出现频率int maxCount = Integer.MIN_VALUE;// 统计频率int count = 0;List<Integer> res = new LinkedList<>();while (!stack.isEmpty() || cur != null) {if (cur != null) {stack.offerLast(cur);cur = cur.left;} else {cur = stack.pollLast();// 当前节点是第一个节点, count 为 1if (pre == null) {count = 1;// 当前节点和前一个节点值相同, count++} else if (pre.val == cur.val) {count++;// 当前节点和前一个节点不同, count 变为 1} else {count = 1;}// 更新 pre 节点pre = cur;// 如果当前统计到的节点值次数和最大节点值次数相同// 就放入列表 resif (count == maxCount) {res.add(cur.val);}// 如果 count > maxCount, 那么就更新 maxCount// 然后先清空 res, 再将当前节点值加入列表 resif (count > maxCount) {maxCount = count;res.clear();res.add(cur.val);}cur = cur.right;}}int[] a = new int[res.size()];for (int i = 0; i < a.length; i++) {a[i] = res.get(i);}return a;
}
时间复杂度:O(n),需要遍历二叉搜索树的所有节点,节点数为 n。
🌏总结
这个题要求我们查找二叉搜索树中的众数,也就是出现次数最多的一个或者多个节点值,按照一般的做法,我们会将二叉搜索树的节点值放到一个数组中,对数组进行排序,然后使用双指针遍历来获取数组中的众数,但是此题我们可以直接在遍历的过程中获取众数,为什么呢?因为根据二叉搜索树的特性,我们知道二叉搜索树的中序序列是一个有序的递增序列,所以我们可以在中序遍历二叉搜索树的时候同时对节点进行操作,从而获取到众数。
同样,在处理节点时,我们采用双指针法,pre 指向上一个遍历过的节点,然后使用当前节点和 pre 指向的节点进行比较,如果相等,则统计变量 count++,否则重置为 1,当然要注意,当我们遍历第一个节点的时候,pre 为 null,这时候 count 也为 1,也就是当前节点出现了一次。
然后每一次遍历之后,我们要将当前节点频次 count 和最大频次 maxCount 作比较,只要相等,就将当前节点值加入结果列表 res,但是有可能当前节点的频次还会增多,这怎么办呢?这就要到一下步骤了,如果当前频次 count 大于 maxCount,那么就更新 maxCount,接着我们要清空 res,这样就避免了出现错误结果的情况,然后将当前节点值加入 res。
以上我也给出了迭代法的代码,和递归代码的逻辑是完全一样的。
作者:花无缺(huawuque404.com)
🌸欢迎
关注我的博客:花无缺-每一个不曾起舞的日子都是对生命的辜负~
🍻一起进步-刷题专栏:【力扣题解】
🥇往期精彩好文:
📢【全网最全爱心代码仓库】
📢【CSS选择器全解指南】
📢【HTML万字详解】
你们的点赞👍 收藏⭐ 留言📝 关注✅
是我持续创作,输出优质内容的最大动力!
谢谢!
相关文章:
【力扣题解】P501-二叉搜索树中的众数-Java题解
👨💻博客主页:花无缺 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 本文由 花无缺 原创 收录于专栏 【力扣题解】 文章目录 【力扣题解】P501-二叉搜索树中的众数-Java题解🌏题目描述💡题解…...
Wnmp本地部署结合内网穿透实现任意浏览器远程访问本地服务
最近,我发现了一个超级强大的人工智能学习网站。它以通俗易懂的方式呈现复杂的概念,而且内容风趣幽默。我觉得它对大家可能会有所帮助,所以我在此分享。点击这里跳转到网站。 文章目录 前言1.Wnmp下载安装2.Wnmp设置3.安装cpolar内网穿透3.1…...
深信服AF防火墙配置SSL VPN
防火墙版本:8.0.85 需提前确认防火墙是是否有SSL VPN的授权,确认授权用户数量 1、确认内外网接口划分 2、网络→SSL VPN,选择内外网接口地址 3、SSL VPN→用户管理→新增一个SSL VPN的用户 4、新增L3VPN资源,类型选择Other&…...
在Spring Cloud中使用Gateway 网关
我们在上述文章中介绍了相关Spring Cloud的五大核心组件,现在我们来了解一下关于Spring Cloud的网关,关于使用网关,我们同时也需要知道他在一个架构中起到的作用,并且,我们需要知道网关具体的相关功能,本篇…...
【Python】配置环境变量
Python配置Windows系统环境变量 打开电脑属性 ——> 高级系统设置 ——> 高级 ——> 环境变量 Python安装目录 D:\Program Files\Python39 winR打开运行,输入cmd打开命令窗口 python -V...
使用.Net nanoFramework 驱动ESP32的OLED显示屏
本文介绍如何使用.Net nanoFramework 驱动ESP32的OLED显示屏。我们将会从最基础的部分开始,逐步深入,让你能够理解并实现整个过程。无论你是初学者还是有一定经验的开发者,这篇文章都会对你有所帮助。 1. 硬件准备 1.1 ESP32开发板 这里我们…...
0基础学习VR全景平台篇第134篇:720VR全景,云台调整节点
相机、云台和脚架全套设备组装完成后需要进行调校才能开始拍摄。这一节,我们将主要介绍云台调整的两个内容:对中心靶、调三点一线。(后附调校原理) 云台部件名称 一、调节准备 (一)对于安装好的云台 1.检…...
扫地机器人地图与用户终端的同步
以下内容为本人的学习笔记,如需要转载,请声明原文链接 微信公众号「ENG八戒」https://mp.weixin.qq.com/s/APaJheSbgTW3jNssWsp5Ng 地图数据来源于机器人算法模块,一般通过SLAM算法完成建图的过程。 建图过程中,基础数据涉及到各…...
使用机器学习进行语法错误检测/纠正
@francescofranco_39234 一、说明 一般的学习,特别是深度学习,促进了自然语言处理。各种模型使人们能够执行机器翻译、文本摘要和情感分析——仅举几个用例。今天,我们将研究另一个流行的用途:我们将使用Gramformer构建一个用于机器学习语法错误检测和纠正的管道。 阅读本文…...
从0到1快速入门ETLCloud
一、ETLCloud的介绍 ETL是将业务系统的数据经过抽取(Extract)、清洗转换(Transform)之后加载(Load)到数据仓库的过程,目的是将企业中的分散、凌乱、标准不统一的数据整合到一起,为企…...
QT上位机开发(会员管理软件)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 前面我们学习了ini文件的解析办法,通过QSettings类就可以很轻松地访问ini文件里面的数据。除了ini文件之外,另外一种经常出…...
线性代数笔记3 1.1
学习视频: 2.2 矩阵运算(二)_哔哩哔哩_bilibili 包括内容: p10矩阵运算(二) p11特殊矩阵 p12逆矩阵(一) p13逆矩阵(二)...
2023年12月编程语言排行榜
TIOBE Index for December 2023 December Headline: C# on its way to become programming language of the year 2023 2023年12月的TIOBE指数:12月头条:c#将成为2023年最佳编程语言 Yes, I know, we have been here before. At the end of 2022, it looked like …...
Redis VS Memcached:选择哪个更适合您的应用?
目录 1、前言 2、概念简介 2.1 Redis 2.2 Memcached 3、数据模型 4、持久性 5、分布式能力 6、性能和扩展性 7、如何选择适合您引用的缓存系统 8、结语 1、前言 Redis和Memcached都是常见的内存缓存系统,用于提升应用程序的性能和可扩展性。它们都具有高…...
【HarmonyOS开发】共享包HAR和HSP的创建和使用以及三方库的发布
OpenHarmony提供了两种共享包,HAR(Harmony Archive)静态共享包,和HSP(Harmony Shared Package)动态共享包。 HAR与HSP都是为了实现代码和资源的共享,都可以包含代码、C库、资源和配置文件&…...
安装 Node.js、npm
安装 nodejs 安装Node.js的最简单的方法是通过软件包管理器。 Node.js官网:https://nodejs.org/en/download/ cd /usr/local/src/wget -c https://nodejs.org/dist/v18.16.0/node-v18.16.0-linux-x64.tar.xz xz -d node-v18.16.0-linux-x64.tar.xz tar -xf node…...
解决报错:找不到显卡
今天做实验碰到一个问题:torch找不到显卡: 打开任务管理器,独显直接没了,一度以为是要去修电脑了,突然想到上次做实验爆显存,屏蔽了gpu用cpu训练: import os os.environ["CUDA_DEVICE_OR…...
如何使用Node.js快速创建本地HTTP服务器并实现公网访问服务端
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
【社交网络分析】课程考试复盘 + 相关资料补充
【社交网络分析】考试后复盘 相关资料补充 写在最前面论述1.描述Logistic回归模型构造损失函数的主要思想。它是如何把线性回归预测模型转化为二分类模型的。Logistic回归模型构造损失函数的主要思想Logistic回归如何将线性回归预测模型转化为二分类模型 2.社交网络分析中面临…...
算法——队列+宽搜(BFS)
队列这种数据结构大都服务于一个算法——宽搜(BFS)。宽搜还可以运用到二叉树、图、迷宫最短路径问题、拓扑排序等等 N叉数的层序遍历 N叉树的层序遍历 题目解析 给定一个 N 叉树,返回其节点值的_层序遍历_。(即从左到右&#…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...
Linux 下 DMA 内存映射浅析
序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存,但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程,可以参考这篇文章,我觉得写的非常…...
热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...
