当前位置:网站首页>Leetcode skimming: binary tree 23 (mode in binary search tree)
Leetcode skimming: binary tree 23 (mode in binary search tree)
2022-07-07 12:48:00 【Taotao can't learn English】
501. The mode in the binary search tree
Given a binary search tree with the same value (BST), find BST All the modes in ( The most frequent element ).
Assume BST It has the following definition :
- The value of the node contained in the left subtree of a node is less than or equal to the value of the current node
- The value of the node contained in the right subtree of a node is greater than or equal to the value of the current node
- Both the left and right subtrees are binary search trees
for example :
Given BST [1,null,2,2],
return [2].
Tips : If the mode exceeds 1 individual , There is no need to consider the output sequence
Advanced : Can you not use extra space ?( Suppose the overhead of implicit call stack generated by recursion is not counted )
Two ways of thinking :
1: General writing method , Hashtable , Traversing the tree , Save the result set to hashmap, Traversal frequency value Get the maximum , Iterate again to get the result set , Process into an array .
HashMap<Integer, Integer> result = new HashMap<Integer, Integer>();
public int[] findMode(TreeNode root) {
// This problem can be done with a hash table
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. Binary search tree writing : Because it's a binary search tree , The decreasing , So the same number must be together , Count the number of occurrences of each number , Give a maximum number of occurrences , If the number of occurrences of the current number is less than the maximum number , Do not change , If equal , Then add the current number to the result set , If it is greater than the maximum number of occurrences , Then empty the result set , The current number is added to the result set .
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 the number of occurrences of the current element is greater than the maximum number , Then a new mode appears , The original is not the mode
if (curTimes > maxTimes) {
maxTimes = curTimes;
list.clear();
list.add(root.val);
} else if (curTimes == maxTimes) {
// If the number of occurrences of the current element is equal to the maximum number , Then a new mode appears
list.add(root.val);
}
} else {
curTimes = 1;
if (curTimes > maxTimes) {
maxTimes = curTimes;
list.clear();
list.add(root.val);
} else if (curTimes == maxTimes) {
// If the number of occurrences of the current element is equal to the maximum number , Then a new mode appears
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;
}
边栏推荐
- leetcode刷题:二叉树19(合并二叉树)
- Pule frog small 5D movie equipment | 5D movie dynamic movie experience hall | VR scenic area cinema equipment
- [statistical learning method] learning notes - logistic regression and maximum entropy model
- 【统计学习方法】学习笔记——支持向量机(上)
- 什么是ESP/MSR 分区,如何建立ESP/MSR 分区
- Session
- MySQL导入SQL文件及常用命令
- Visual stdio 2017 about the environment configuration of opencv4.1
- 2022a special equipment related management (boiler, pressure vessel and pressure pipeline) simulated examination question bank simulated examination platform operation
- [Q&A]AttributeError: module ‘signal‘ has no attribute ‘SIGALRM‘
猜你喜欢
leetcode刷题:二叉树19(合并二叉树)
[statistical learning methods] learning notes - Chapter 5: Decision Tree
Importance of database security
Sorting, dichotomy
HZOJ #240. 图形打印四
Vxlan 静态集中网关
SQL lab 11~20 summary (subsequent continuous update) contains the solution that Firefox can't catch local packages after 18 levels
leetcode刷题:二叉树23(二叉搜索树中的众数)
[pytorch practice] write poetry with RNN
Day-15 common APIs and exception mechanisms
随机推荐
用mysql查询某字段是否有索引
[pytorch practice] use pytorch to realize image style migration based on neural network
普乐蛙小型5d电影设备|5d电影动感电影体验馆|VR景区影院设备
解密GD32 MCU产品家族,开发板该怎么选?
[爬虫]使用selenium时,躲避脚本检测
SQL lab 21~25 summary (subsequent continuous update) (including secondary injection explanation)
ACL 2022 | small sample ner of sequence annotation: dual tower Bert model integrating tag semantics
广州市召开安全生产工作会议
2022-07-07日报:GAN发明者Ian Goodfellow正式加入DeepMind
SQL head injection -- injection principle and essence
Day-15 common APIs and exception mechanisms
金融数据获取(三)当爬虫遇上要鼠标滚轮滚动才会刷新数据的网页(保姆级教程)
2022 examination questions and online simulation examination for safety production management personnel of hazardous chemical production units
gcc 编译报错
Connect to blog method, overload, recursion
File upload vulnerability - upload labs (1~2)
[learn microservices from 0] [03] explore the microservice architecture
visual stdio 2017关于opencv4.1的环境配置
[statistical learning methods] learning notes - Chapter 5: Decision Tree
test