501. Find Mode in Binary Search Tree查找BST中的众数
2024-09-04 10:54:11
[抄题]:
Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than or equal to the node's key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
- Both the left and right subtrees must also be binary search trees.
For example:
Given BST [1,null,2,2]
,
1
\
2
/
2
return [2]
.
[暴力解法]:
时间分析:
空间分析:hashmap:n
[优化后]:
时间分析:
空间分析:各种count
[奇葩输出条件]:
返回具体元素,不是次数。所以反过来 nums[次数] = 元素。
[奇葩corner case]:
[思维问题]:
[一句话思路]:
curcount > maxcount时,重置modecount = 1
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- 要处理的情况写if, else if,不处理的不用管
- inorder遍历本质是dfs,也有退出条件
[二刷]:
- maxcount最大值需要保留,不能清空
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
curcount > maxcount时,更改众数,重置modecount = 1
[复杂度]:Time complexity: O(n) Space complexity: O(1)
[英文数据结构或算法,为什么不用别的数据结构或算法]:
- 全局变量用于声明类型 一次就行 eg int,有返回值的单个函数中赋值
[关键模板化代码]:
if (curCount > maxCount) {
maxCount = curCount;
modeCount = 1;
}else if (curCount == maxCount) {
if (modes != null) //after first inorder
modes[modeCount] = curValue;
modeCount ++;
}
}
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
[代码风格] :
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//ini
private int curValue;
private int[] modes;
private int curCount = 0;
private int maxCount = 0;
private int modeCount = 0; public int[] findMode(TreeNode root) {
//inorder twice
inorder(root);
modes = new int [modeCount];
curCount = 0;
//maxCount = 0;need jilu
modeCount = 0;//re start
inorder(root);
return modes;
} public void handleValue(int val) {
if (val != curValue) {
curValue = val;
curCount = 0;
}
curCount++; if (curCount > maxCount) {
maxCount = curCount;
modeCount = 1;
}else if (curCount == maxCount) {
if (modes != null) //after first inorder
modes[modeCount] = curValue;
modeCount ++;
}
} public void inorder(TreeNode root) {
if (root == null) return ;
inorder(root.left);
handleValue(root.val);
inorder(root.right);
}
}
最新文章
- 前端开发--css属性书写顺序
- python 迭代器和生成器
- 【转】为什么很多看起来不是很复杂的网站,比如 Facebook、淘宝,都需要大量顶尖高手来开发?
- Spring-JDBC通用Dao
- Linux Shell入门(转载)
- 关于arcgis 9.3破解问题详解
- ASP.NET中常用重置数据的方法
- Oracle ACL (Access Control List)详解
- ARM编译空间属性(转)
- Maven 打包到Tomcat下
- jQuery滚动广告 解决子div绝对定位与父div重叠引起的闪烁问题
- sql学习之基础(MySql)
- JS Bin Tips and Bits • About
- endnote X7使用方法
- mongodb副本集高可用架构
- Python学习之旅(二十八)
- ADB server didn't ACK failed to start daemon 5037
- 学JS的心路历程 -物件与原型(二)
- python_循环(迭代)
- RUP