( “树” 之 BST) 501. 二叉搜索树中的众数 ——【Leetcode每日一题】

news/2024/2/28 11:43:19

二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。
二叉查找树中序遍历有序。

❓501. 二叉搜索树中的众数

难度:简单

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

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

假定 BST 满足如下定义:

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

示例 1:

在这里插入图片描述

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

示例 2:

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

提示:

  • 树中节点的数目在范围 [ 1 , 1 0 4 ] [1, 10^4] [1,104]
  • − 1 0 5 < = N o d e . v a l < = 1 0 5 -10^5 <= Node.val <= 10^5 105<=Node.val<=105

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

💡思路:

中序遍历,边遍历边统计:

要设置三个变量:curCnt表示当前个数;maxCnt表示最大个数;preNode表示前一个结点:

  • 如果当前结点值等于前一个结点值,则curCnt++,否则curCnt置为1重新计数;
  • 如果当前个数curCnt大于最大个数maxCnt,则将数组清空,添加当前节点值;
  • 如果当前个数curCnt大于最大个数maxCnt,则不需要清空,在数组后面添加就行;

🍁代码:(Java、C++)

Java

class Solution {private int curCnt = 1;private int maxCnt = 1;private TreeNode preNode = null;public int[] findMode(TreeNode root) {List<Integer> maxCntNums = new ArrayList<>();inOrder(root, maxCntNums);int[] ret = new int[maxCntNums.size()];int idx = 0;for (int num : maxCntNums) {ret[idx++] = num;}return ret;}private void inOrder(TreeNode node, List<Integer> nums) {if (node == null) return;inOrder(node.left, nums);if (preNode != null) {if (preNode.val == node.val) curCnt++;else curCnt = 1;}if (curCnt > maxCnt) {maxCnt = curCnt;nums.clear();nums.add(node.val);} else if (curCnt == maxCnt) {nums.add(node.val);}preNode = node;inOrder(node.right, nums);}
}

C++

class Solution {
public:int curCnt = 1;int maxCnt = 1;TreeNode* preNode = nullptr;vector<int> findMode(TreeNode* root) {vector<int> ans;inOrder(root, ans);return ans;}void inOrder(TreeNode* root, vector<int>& ans){if(root == nullptr) return;inOrder(root->left, ans);if(preNode != nullptr){if(root->val == preNode->val) curCnt++;else curCnt = 1;}if(curCnt > maxCnt){maxCnt = curCnt;ans.clear();ans.push_back(root->val);}else if(curCnt == maxCnt){ans.push_back(root->val);}preNode = root;inOrder(root->right, ans);}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n):即遍历这棵树的复杂度。
  • 空间复杂度 O ( 1 ) O(1) O(1):如果调用栈的开销不被计算在内,储存结果的数组也不计算,空间复杂度为 O ( 1 ) O(1) O(1)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/52718.html

相关文章

有效的字母异位词

给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意&#xff1a;若 s 和 t 中每个字符出现的次数都相同&#xff0c;则称 s 和 t 互为字母异位词。 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;https://leetco…

Spring Bean生命周期源码详解

文章目录 Bean生命周期源码生成BeanDefinitionSpring容器启动时创建单例Bean合并BeanDefinitiongetBean()方法加载类实例化前实例化BeanDefinition的后置处理实例化后依赖注入执行Aware回调初始化前初始化初始化后销毁逻辑 Bean生命周期源码 我们创建一个ApplicationContext对…

Elasticsearch简单搜索以及聚合分析

1.批量索引文档 如果你有大量文档要索引&#xff0c;你能通过批量 API&#xff08;bulk API&#xff09; 来批量提交它们。批量文档操作比单独提交请求显著更快&#xff0c;因为它极简了网络往返。 最佳的批量数量取决于许多因素&#xff1a;文档的大小和复杂度、索引和搜索的…

OJ练习第84题——按字典序排在最后的子串

按字典序排在最后的子串 力扣链接&#xff1a;1163. 按字典序排在最后的子串 题目描述 给你一个字符串 s &#xff0c;找出它的所有子串并按字典序排列&#xff0c;返回排在最后的那个子串。 示例 示例 1&#xff1a; 输入&#xff1a;s “abab” 输出&#xff1a;“bab…

5.2 构造数值积分公式的基本方法与有关概念的例题分析

书上例题&#xff1a; 例3 确定求积公式 中的系数&#xff0c;使其具有尽可能高的代数精度。 我的答案&#xff1a; 一、信息 1.给了我一个求积公式 2.确定求积公式中的系数 3.使得这个求积系数具有尽可能高的代数精度。 二、分析 条件1&#xff1a;告诉我这个求积公…

全新推出!赛宁BAS智能安全验证,让企业安全系统坚如磐石

赛宁BAS智能安全验证系统&#xff0c;可以通过模拟网络攻击来检验安全防御手段有效性&#xff0c;量化安全风险并给出安全加固建议&#xff0c;帮助行业客户降低安全运营成本&#xff0c;提升网络安全防御能力。 一、解析安全防御现状 在合规时代背景下&#xff0c;虽然大部分…

AI 时代的学习方式: 和文档对话

作者&#xff1a;明明如月学长&#xff0c; CSDN 博客专家&#xff0c;蚂蚁集团高级 Java 工程师&#xff0c;《性能优化方法论》作者、《解锁大厂思维&#xff1a;剖析《阿里巴巴Java开发手册》》、《再学经典&#xff1a;《EffectiveJava》独家解析》专栏作者。 热门文章推荐…

WeakHashMap的应用场景

WeakHashMap&#xff0c;从名字可以看出它是某种 Map。它的特殊之处在于 WeakHashMap 里的entry可能会被GC自动删除&#xff0c;即使程序员没有调用remove()或者clear()方法。 1、适用于缓存场景 更直观的说&#xff0c;当使用 WeakHashMap 时&#xff0c;即使没有显示的添加或…

【LeetCode: 5. 最长回文子串 | 暴力递归=>记忆化搜索=>动态规划 => 中心扩展法】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

从零学习SDK(9)SDK的局限

SDK是一种便捷而实用的工具&#xff0c;但软件开发者不能视SDK为万能的解决之道&#xff0c;SDK也有局限性&#xff0c;并且这些局限性可能会十分“致命”。软件开发者在选择SDK产品之前&#xff0c;需要先了解SDK的不足之处。本文将介绍SDK存在的三种问题&#xff0c;以引起软…

收藏!亚马逊29条选品思路!新手小白避坑指南!

亚马逊卖家如何选择产品一直是最令人困惑的问题&#xff0c;甚至比选择目标受众更难。如果他们选择不好&#xff0c;他们就不会卖出&#xff0c;如果他们选择不对&#xff0c;就不会有任何利润空间。那么如何选择产品呢&#xff1f;是从消费者的角度还是从产品的角度&#xff1…

Java项目上线之云服务器环境篇(二)——Tomcat的安装与配置

Java项目上线之云服务器环境篇&#xff08;二&#xff09;——Tomcat的安装与配置 Tomcat的选择&#xff1a; 云服务器tomcat的选择最好与本机项目运行的tomcat版本号一致&#xff0c;避免一些不必要的问题。 配置步骤&#xff1a; 1、首先进入云服务器创建好放置tomcat的文件…

LeetCode 18. 四数之和

LeetCode 18. 四数之和 题目描述 给定一个包含 n 个整数的数组 nums 和一个目标值 target&#xff0c;判断 nums 中是否存在四个元素 a&#xff0c;b&#xff0c;c 和 d &#xff0c;使得 a b c d 的值与 target 相等&#xff1f;找出所有满足条件且不重复的四元组。 注意…

【Apple Studio Display】苹果显示器无法连接Dell 5488

【Apple Studio Display】苹果显示器无法连接Dell 5488 &#xff08;1&#xff09;Dell 5488 could not use the Apple studio display via the type-c cable The Dell Latitude 5488 laptop has a USB Type-C port that supports DisplayPort Alternate Mode, which allows …

优化Dynamics 365建议

传统上&#xff0c;旧版 Web 客户端需要某些扩展&#xff08;如功能区规则&#xff09;同步返回&#xff0c;这意味着开发人员在从远程源请求数据时被迫使用同步请求。在统一接口中&#xff0c;我们已采取措施确保支持异步通信。例如&#xff1a; 统一接口支持异步功能区规则评…

面向对象(六)-- 接口

目录 1. 接口的概述 2. 接口的特点(重要记忆) 3. 接口的成员特点(重要记忆)

NEFU-2023-算法设计与分析实验二动态规划算法设计

作者的话 大底包含了算法硬性规定的作业代码&#xff0c;并非最优解&#xff0c;仅供参考并会持续更新。勿要无脑copy&#xff0c;对自己负责。如果代码有误或者优化建议&#xff0c;直接相应博客下方评论或者qq找我如果对代码有理解不了的或者疑惑可以询问我&#xff0c;但是…

8 DWA(一)

8 DWA DMA简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取&#xff08;可以直接访问32内部存储器&#xff0c;包括内存SRAM&#xff0c;Flash&#xff09; DMA可以提供外设和存储器或者存储器和存储器之间的高速数据传输&#xff0c;无须CPU干预&#x…

项目管理-项目经理的5种权力

1、项目团队&#xff1a;是执行项目工作&#xff0c;以实现项目目标的一组人员&#xff0c;由为了完成项目而承担不同角色与职责的人员组成。 项目团队成员可能具备不同的技能&#xff0c;可能是全职的或兼职的&#xff0c;也可能随项目进展而增加或减少。尽管项目团队成员被分…

JDBC重点

JDBC初识 DriverManager 将第三方数据库厂商的实现驱动jar注册到程序中可以根据数据库连接信息获取connection Connection 和数据库建立的连接,在连接对象上,可以多次执行数据库curd动作 可以获取statement和 preparedstatement,callablestatement对象 Statement | Prepare…
最新文章