当前位置:网站首页>LC501. Mode in binary search tree
LC501. Mode in binary search tree
2022-07-01 22:38:00 【996 Chong Chong】
Violent calculation mode , Spatial complexity O(N), Because an array is used to store the results of the middle order traversal
Then it is the ordered array to find the mode , In fact, this does not use the characteristics of binary search tree .
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) # Count the number of each element with a dictionary
for i in res:
d[i] += 1
x = sorted(d.values())
max = x[-1] # Get the most elements
for i in d.items():
if i[1] == max:
sol.append(i[0]) # Add the corresponding key to the answer
return sol
Spatial complexity O(1) Methods
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) # Using the property that middle order is order , Add processing logic in the middle order
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: # Cannot be empty when equal to , So add this sentence
self.res.append(root.val)
if self.count > self.maxcount: # When it is larger than, it needs to be changed , So you need to empty it and re append
self.maxcount = self.count
self.res = []
self.res.append(root.val)
inorder(root.right)
inorder(root)
return self.res
边栏推荐
- Communication between browser tab pages
- QT 使用FFmpeg4将argb的Qimage转换成YUV422P
- 性能测试计划怎么编写
- awoo‘s Favorite Problem(优先队列)
- Sonic云真机学习总结6 - 1.4.1服务端、agent端部署
- Learning notes on futuretask source code of concurrent programming series
- 【目标跟踪】|单目标跟踪指标
- Smart micro mm32 multi-channel adc-dma configuration
- 【日常训练】326. 3 的幂
- #yyds干货盘点# 解决名企真题:扭蛋机
猜你喜欢
随机推荐
[monomer] recommended configuration of streaming information i-bpsv3 server
MySQL数据库详细学习教程
QT uses ffmpeg4 to convert the qimage of ARGB to yuv422p
Show member variables and methods in classes in idea
Four methods of JS array splicing [easy to understand]
keras训练的H5模型转tflite
Unity 使用Sqlite
awoo‘s Favorite Problem(优先队列)
H5 model trained by keras to tflite
Can you get a raise? Analysis on gold content of PMP certificate
内存导致的电脑游戏中显示hdmi无信号 从而死机的情况
[jetcache] how to use jetcache
Fully annotated SSM framework construction
A debugging to understand the slot mechanism of redis cluster
MySQL series transaction log redo log learning notes
Recent public ancestor offline practice (tarjan)
【MySQL】explain的基本使用以及各列的作用
【日常训练】66. 加一
功能测试报告的编写
Dark horse programmer - software testing - stage 06 2-linux and database-01-08 Chapter 1 - description of the content of the Linux operating system stage, description of the basic format and common fo