501. Find Mode in Binary Search Tree

#### QUESTION:

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

#### EXPLANATION:

1.遍历二叉树

2.如果与前面一个数相同则count+1，否则count= 1；

3.如果count大于max说明出现了更多的数，则清除数组，更新最多的数

4.修改prev的数。

#### SOLUTION:

``````public class Solution {
Integer prev = null;
int count = 1;
int max = 0;
public int[] findMode(TreeNode root) {
if(root == null) return new int;
ArrayList<Integer> resultList = new ArrayList<>();
findModeHelper(root,resultList);
int[] resultarray = new int[resultList.size()];
for(int i = 0;i<resultarray.length;i++){
resultarray[i] = resultList.get(i);
}
return resultarray;
}

private void findModeHelper(TreeNode root, List<Integer> result) {
if(root==null) return;
findModeHelper(root.left,result);
if(prev!=null){
if(root.val == prev){
count++;
}else{
count = 1;
}
}
if(count > max){
max = count;
result.clear();