当前位置:网站首页>leetcode刷题:二叉树23(二叉搜索树中的众数)
leetcode刷题:二叉树23(二叉搜索树中的众数)
2022-07-07 10:30:00 【涛涛英语学不进去】
501.二叉搜索树中的众数
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
假定 BST 有如下定义:
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如:
给定 BST [1,null,2,2],
返回[2].
提示:如果众数超过1个,不需考虑输出顺序
进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
两种思路:
1: 通用写法,哈希表,遍历树,把结果集存到hashmap,遍历频率value获取最大值,再遍历一遍获取结果集,处理成数组。
HashMap<Integer, Integer> result = new HashMap<Integer, Integer>();
public int[] findMode(TreeNode root) {
//本题可以使用哈希表做
traversal(root);
Set<Integer> keys = result.keySet();
int max = -1;
for (Integer key : keys) {
if (result.get(key) > max) {
max = result.get(key);
}
}
Set<Integer> resultSet = new HashSet<Integer>();
for (Integer key : keys) {
if (result.get(key) == max) {
resultSet.add(key);
}
}
int[] resultArr = new int[resultSet.size()];
int index = 0;
for (Integer key : resultSet) {
resultArr[index] = key;
index++;
}
return resultArr;
}
public void traversal(TreeNode root) {
if (root == null) {
return;
}
traversal(root.left);
if (result.containsKey(root.val)) {
result.put(root.val, result.get(root.val) + 1);
} else {
result.put(root.val, 1);
}
traversal(root.right);
}
2.二叉搜索树写法:因为是二叉搜索树,非递减,所以一样的数肯定都是在一块的,计算每个数出现的次数,给一个最大出现次数,如果当前数出现次数比最大出现次数小,不做改变,若相等,则把当前数添加到结果集,如果比最大出现次数大,则清空结果集,当前数添加到结果集。
List<Integer> list = new ArrayList<>();
TreeNode parent;
int maxTimes = 0;
int curTimes = 0;
public void inorderTraversal(TreeNode root) {
if (root == null) {
return;
}
inorderTraversal(root.left);
if (root.val == parent.val) {
curTimes++;
//如果当前元素出现次数比最大次数大,则新的众数出现,原来的不是众数了
if (curTimes > maxTimes) {
maxTimes = curTimes;
list.clear();
list.add(root.val);
} else if (curTimes == maxTimes) {
//如果当前元素出现次数和最大次数相等,则新的众数出现
list.add(root.val);
}
} else {
curTimes = 1;
if (curTimes > maxTimes) {
maxTimes = curTimes;
list.clear();
list.add(root.val);
} else if (curTimes == maxTimes) {
//如果当前元素出现次数和最大次数相等,则新的众数出现
list.add(root.val);
}
parent = root;
}
inorderTraversal(root.right);
}
public int[] findMode(TreeNode root) {
parent = root;
inorderTraversal(root);
int index = 0;
int[] resultArr = new int[list.size()];
for (Integer result : list) {
resultArr[index] = result;
index++;
}
return resultArr;
}
边栏推荐
- Sign up now | oar hacker marathon phase III midsummer debut, waiting for you to challenge
- 千人规模互联网公司研发效能成功之路
- Tutorial on the principle and application of database system (008) -- exercises on database related concepts
- The left-hand side of an assignment expression may not be an optional property access. ts(2779)
- 免备案服务器会影响网站排名和权重吗?
- 2022 年第八届“认证杯”中国高校风险管理与控制能力挑战赛
- What is an esp/msr partition and how to create an esp/msr partition
- <No. 8> 1816. Truncate sentences (simple)
- "Series after reading" my God! It's so simple to understand throttling and anti shake~
- PowerShell cs-utf-16le code goes online
猜你喜欢
Sign up now | oar hacker marathon phase III midsummer debut, waiting for you to challenge
Hi3516 full system type burning tutorial
Attack and defense world - PWN learning notes
Xiaohongshu microservice framework and governance and other cloud native business architecture evolution cases
什么是ESP/MSR 分区,如何建立ESP/MSR 分区
(待会删)yyds,付费搞来的学术资源,请低调使用!
College entrance examination composition, high-frequency mention of science and Technology
Review and arrangement of HCIA
What is an esp/msr partition and how to create an esp/msr partition
Minimalist movie website
随机推荐
Decrypt gd32 MCU product family, how to choose the development board?
Inverted index of ES underlying principle
Introduction to three methods of anti red domain name generation
SQL Lab (32~35) contains the principle understanding and precautions of wide byte injection (continuously updated later)
免备案服务器会影响网站排名和权重吗?
An error occurred when vscade tried to create a file in the target directory: access denied [resolved]
gcc 编译报错
What are the top-level domain names? How is it classified?
EPP+DIS学习之路(1)——Hello world!
Customize the web service configuration file
源代码防泄密中的技术区别再哪里
SQL Lab (46~53) (continuous update later) order by injection
What is a LAN domain name? How to parse?
@Bean与@Component用在同一个类上,会怎么样?
[play RT thread] RT thread Studio - key control motor forward and reverse rotation, buzzer
Ctfhub -web SSRF summary (excluding fastcgi and redI) super detailed
Cenos openssh upgrade to version 8.4
About web content security policy directive some test cases specified through meta elements
MPLS experiment
平安证券手机行开户安全吗?