# LeetCode: 501. Find Mode in Binary Search Tree

## 题目¶

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).

## 解法¶

### 中序遍历统计各个值出现的次数，然后找出次数最多的节点¶

```def inorder(root):
if root is None:
return
inorder(root.left)

# print(root)

inorder(root.right)
```

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def findMode(self, root):
self.count = 0
self.count_val = None
self.max_count = 0
self.vals = []

self.inorder(root)
return self.vals

def inorder(self, root):
if root is None:
return

self.inorder(root.left)

if self.count_val is None:
self.count_val = root.val
if self.count_val == root.val:
self.count += 1
else:
self.count_val = root.val
self.count = 1

if self.count > self.max_count:
self.max_count = self.count
self.vals.clear()

if self.count == self.max_count:
self.vals.append(root.val)

self.inorder(root.right)
```