# 501. Find Mode in Binary Search Tree 二叉搜索树中的众数

@TOC

## # 题目描述

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 [2].
``````

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

## # 解题方法

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def findMode(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root: return []
self.count = collections.Counter()
self.inOrder(root)
freq = max(self.count.values())
res = []
for item, c in self.count.items():
if c == freq:
res.append(item)
return res

def inOrder(self, root):
if not root:
return
self.inOrder(root.left)
self.count[root.val] += 1
self.inOrder(root.right)
``````

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int[] findMode(TreeNode root) {
inOrder(root);
modes = new int[modeCount];
currCount = 0;
modeCount = 0;
inOrder(root);
return modes;
}

int currVal = 0;
int currCount = 0;
int maxCount = 0;
int modeCount = 0;

int[] modes;

public void handleValue(int val){
if(currVal != val){
currVal = val;
currCount = 0;
}
currCount++;
if(currCount > maxCount){
maxCount = currCount;
modeCount = 1;
}else if (currCount == maxCount){
if(modes != null){
modes[modeCount] = currVal;
}
modeCount++;
}
}

public void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
handleValue(root.val);
inOrder(root.right);
}
}
``````

## # 日期

2017 年 5 月 3 日 2018 年 11 月 23 日 —— 这就星期五了？？