blob: b53ed6111f1d36822fca0616bacd12a3a3f364bc (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
# 501. Find Mode in Binary Search Tree
"""
given the 'root' of a binary search tree with duplicates, return all the
'modes(s)' (ie. the most frequently occured element in it). if the tree has
more than one mode, return them in any order.
"""
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
prev = None
max_cnt = 0
curr_cnt = 0
ans = []
def dfs(self, node):
if not node:
return
self.dfs(node.left)
self.curr_cnt = 1 if node.val != self.prev else self.curr_cnt + 1
if self.curr_cnt == self.max_cnt:
self.ans.append(node.val)
elif self.curr_cnt > self.max_cnt:
self.ans = [node.val]
self.max_cnt = self.curr_cnt
self.prev = node.val
self.dfs(node.right)
def findMode(self, root):
self.dfs(root)
return self.ans
if __name__ == "__main__":
obj = Solution()
print(obj.findMode([1, None, 2, 2])) # expect: 2
print(obj.findMode([0])) # expect: 0
|