## Description

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 .

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

## Solutions

### 1. Inorder traversal

# Time: O(nlogn)
# Space: O(n)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def findMode(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = []
node = root
hash_map = {}
max_val = float('-inf')
res = []
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
hash_map[node.val] = hash_map.get(node.val, 0) + 1
max_val = max(hash_map[node.val], max_val)
node = node.right
for key, value in hash_map.items():
if value == max_val:
res.append(key)
return res

# 25/25 cases passed (56 ms)
# Your runtime beats 65.56 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (16.6 MB)


### 2. Space O(1)

一直没找到改成 python 后错在哪儿……

class Solution:
def findMode(self, root: TreeNode) -> List[int]:
if not root:
return []
pre_node = None
max_val, cnt = , 
res = []
self.inorder(root, pre_node, cnt, max_val, res)
return res

def inorder(self, node, pre_node, cnt, max_val, res):
if not node:
return
self.inorder(node.left, pre_node, cnt, max_val, res)
if pre_node:
if node.val == pre_node.val:
cnt += 1
else:
cnt = 1
print(res, cnt, max_val)
if cnt >= max_val:
if cnt > max_val:
res.clear()
res.append(node.val)
max_val = cnt

pre_node = node
self.inorder(node.right, pre_node, cnt, max_val, res)


不想看了，有点儿烦躁了……

class Solution(object):
def findMode(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
def inorder(root, prev, cnt, max_cnt, result):
if not root:
return prev, cnt, max_cnt

prev, cnt, max_cnt = inorder(root.left, prev, cnt, max_cnt, result)
if prev:
if root.val == prev.val:
cnt += 1
else:
cnt = 1
if cnt > max_cnt:
max_cnt = cnt
del result[:]
result.append(root.val)
elif cnt == max_cnt:
result.append(root.val)
return inorder(root.right, root, cnt, max_cnt, result)

if not root:
return []
result = []
inorder(root, None, 1, 0, result)
return result
# 25/25 cases passed (60 ms)
# Your runtime beats 39.26 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (16.5 MB)