当前位置:网站首页>Find the mode in the binary search tree (use medium order traversal as an ordered array)
Find the mode in the binary search tree (use medium order traversal as an ordered array)
2022-07-07 08:04:00 【Hydrion-Qlz】
501. The mode in the binary search tree
The difficulty is simple
Give you a binary search tree with duplicate values (BST) The root node root
, Find out and return to BST All in The number of ( namely , The most frequent element ).
If there is more than one mode in the tree , Can press In any order return .
Assume BST Meet the following definitions :
- The value of the node contained in the left subtree of the node Less than or equal to The value of the current node
- The value of the node contained in the right subtree of the node Greater than or equal to The value of the current node
- Both the left and right subtrees are binary search trees
Ideas
The definition here is similar to what we usually encounter BST The definition of is different , Therefore, it should be clear that values equal to the current node may appear in both the left subtree and the right subtree , So it is very difficult to deal with recursion alone
But I am As mentioned in a previous question , Traverse the binary search tree , What you get is an ordered array .
Find the mode on an ordered array , Isn't it easy to catch ?
If you really don't understand it, you can go through the middle order first and add all the elements to an array , Then find the mode on the array
Of course, it is not recommended , This will lead to low time efficiency
package cn.edu.xjtu.carlWay.tree.findModeInBST;
import cn.edu.xjtu.Util.TreeNode.TreeNode;
import java.util.ArrayList;
import java.util.List;
/** * 501. The mode in the binary search tree * Give you a binary search tree with duplicate values (BST) The root node root , Find out and return to BST All in The number of ( namely , The most frequent element ). * <p> * If there is more than one mode in the tree , Can press In any order return . * <p> * Assume BST Meet the following definitions : * <p> * The value of the node contained in the left subtree of the node Less than or equal to The value of the current node * The value of the node contained in the right subtree of the node Greater than or equal to The value of the current node * Both the left and right subtrees are binary search trees * <p> * https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/ */
public class Solution {
List<Integer> result = new ArrayList<>();
int maxNum = 0;
TreeNode pre;
int count = 0;
public int[] findMode(TreeNode root) {
if (root == null) return null;
traversal(root);
int[] ret = new int[result.size()];
for (int i = 0; i < ret.length; i++) {
ret[i] = result.get(i);
}
return ret;
}
private void traversal(TreeNode root) {
if (root == null) return;
// Recursive left subtree
traversal(root.left);
// Processing data
if (pre == null || root.val != pre.val) {
count = 1;
} else {
count++;
}
if (count > maxNum) {
result.clear();
result.add(root.val);
maxNum = count;
} else if (count == maxNum) {
result.add(root.val);
}
pre = root;
// Recursive right subtree
traversal(root.right);
}
}
边栏推荐
- Button wizard collection learning - mineral medicine collection and running map
- 芯片 设计资料下载
- Ansible
- 2022年茶艺师(中级)考试试题及模拟考试
- Summary of redis functions
- Linux Installation MySQL 8.0 configuration
- Avatary的LiveDriver试用体验
- Introduction to basic components of wechat applet
- [quickstart to Digital IC Validation] 15. Basic syntax for SystemVerilog Learning 2 (operator, type conversion, loop, Task / Function... Including practical exercises)
- 大视频文件的缓冲播放原理以及实现
猜你喜欢
Record a stroke skin bone error of the skirt
Force buckle 144 Preorder traversal of binary tree
开源生态|打造活力开源社区,共建开源新生态!
快速使用 Jacoco 代码覆盖率统计
Es FAQ summary
[unity] several ideas about circular motion of objects
[quickstart to Digital IC Validation] 15. Basic syntax for SystemVerilog Learning 2 (operator, type conversion, loop, Task / Function... Including practical exercises)
Quickly use Jacobo code coverage statistics
Open source ecosystem | create a vibrant open source community and jointly build a new open source ecosystem!
Thinkcmf6.0 installation tutorial
随机推荐
[UVM practice] Chapter 1: configuring the UVM environment (taking VCs as an example), run through the examples in the book
[UVM practice] Chapter 2: a simple UVM verification platform (2) only driver verification platform
Operation suggestions for today's spot Silver
Pytorch parameter initialization
贝叶斯定律
Qt学习27 应用程序中的主窗口
让Livelink初始Pose与动捕演员一致
[quick start of Digital IC Verification] 17. Basic grammar of SystemVerilog learning 4 (randomization)
DNS server configuration
Quickly use Jacobo code coverage statistics
Visualization Document Feb 12 16:42
Force buckle 144 Preorder traversal of binary tree
Téléchargement des données de conception des puces
MySQL multi column index (composite index) features and usage scenarios
[quick start of Digital IC Verification] 15. Basic syntax of SystemVerilog learning 2 (operators, type conversion, loops, task/function... Including practical exercises)
Chip design data download
mysql多列索引(组合索引)特点和使用场景
The charm of SQL optimization! From 30248s to 0.001s
[Matlab] Simulink 自定义函数中的矩阵乘法工作不正常时可以使用模块库中的矩阵乘法模块代替
B. Value sequence thinking