当前位置:网站首页>LC501. 二叉搜索树中的众数
LC501. 二叉搜索树中的众数
2022-07-01 21:45:00 【996冲冲冲】
暴力计算众数,空间复杂度O(N),因为用了一个数组存储中序遍历的结果
之后就是有序数组求众数了,这其实没有用到二叉搜索树的特性。
class Solution(object):
def findMode(self, root):
""" :type root: TreeNode :rtype: List[int] """
sol = []
res = []
def inorder(root):
if not root:
return
inorder(root.left)
res.append(root.val)
inorder(root.right)
inorder(root)
d = collections.defaultdict(int) #用一个字典统计各个元素的数量
for i in res:
d[i] += 1
x = sorted(d.values())
max = x[-1] #获取最多的那个元素
for i in d.items():
if i[1] == max:
sol.append(i[0]) #将对应的键加入答案
return sol
空间复杂度O(1)的方法
def findMode(self, root):
""" :type root: TreeNode :rtype: List[int] """
self.count = 0
self.maxcount = 0
self.res = []
self.pre = None
def inorder(root):
if not root:
return
inorder(root.left) #利用中序是有序的性质,在中序位置加入处理逻辑
if self.pre == None:
self.count = 1
elif root.val == self.pre.val:
self.count += 1
else:
self.count = 1
self.pre = root
if self.count == self.maxcount: #等于的时候不能置空,所以要加上这一句
self.res.append(root.val)
if self.count > self.maxcount: #大于的时候就需要换,所以需要置空并且重新append
self.maxcount = self.count
self.res = []
self.res.append(root.val)
inorder(root.right)
inorder(root)
return self.res
边栏推荐
- plantuml介绍与使用
- Burpsuite simple packet capturing tutorial [easy to understand]
- PHP reflective XSS, reflective XSS test and repair
- Make a three digit number of all daffodils "recommended collection"
- Application of real estate management based on 3D GIS
- JS how to get a list of elements in a collection object
- linux下清理系统缓存并释放内存
- 指标陷阱:IT领导者易犯的七个KPI错误
- Qtreeview+qabstractitemmodel custom model: the third of a series of tutorials [easy to understand]
- I received a letter from CTO inviting me to interview machine learning engineer
猜你喜欢
linux下清理系统缓存并释放内存
Design and practice of new generation cloud native database
快乐数[环类问题之快慢指针]
MySQL series transaction log redo log learning notes
二叉树的基本操作
MIT|256KB 内存下的设备上训练
Microsoft, Columbia University | Godel: large scale pre training of goal oriented dialogue
Pytest Collection (2) - mode de fonctionnement pytest
Why does blocprovider feel similar to provider?
plantuml介绍与使用
随机推荐
Talking from mlperf: how to lead the next wave of AI accelerator
MySQL learning notes - SQL optimization of optimization
Test cancellation 1
牛客月赛-分组求对数和
I received a letter from CTO inviting me to interview machine learning engineer
对象内存布局
Burpsuite simple packet capturing tutorial [easy to understand]
PyTorch磨刀篇|argmax和argmin函数
#yyds干货盘点# 解决名企真题:扭蛋机
记录一次spark on yarn 任务报错 Operation category READ is not supported in state standby
Using closures to switch toggle by clicking a button
Copy ‘XXXX‘ to effectively final temp variable
AIDL基本使用
require与import的区别和使用
Aidl basic use
The difference between NiO and traditional IO
Case of camera opening by tour
【单体】流辰信息I-BPSv3服务器推荐配置
高攀不起的希尔排序,直接插入排序
Clean up system cache and free memory under Linux