題目：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 [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).
一個(gè)二叉搜索樹(shù)羹幸，返回出現(xiàn)最多次數(shù)的value铛漓。
第一個(gè)想法是用HashMap炫欺，既可以查重，又可以計(jì)算次數(shù)罕容，然而不符合follow up不用額外空間的要求，也沒(méi)有利用到二叉搜索樹(shù)的性質(zhì)迫皱。
那么就是迭代了摊腋。對(duì)二叉搜索樹(shù)，使用中序遍歷可以完成值從小到大的遍歷哈雏。這樣相同的value必然連在一起楞件，遇到一個(gè)不同于之前 value的node衫生，就可以比較上一個(gè)value是否是最多次的value。
但是這題的陷阱和要注意的點(diǎn)非常多土浸！
1.可能出現(xiàn)有多個(gè)次數(shù)相同的value的情況罪针，但不知道會(huì)有幾個(gè)，所以先用list暫存黄伊。
比如這樣的情況：[1,1,2,null,null,null,2]
2.最后一個(gè)value的次數(shù)判斷要回到主函數(shù)泪酱，因?yàn)楹罄m(xù)沒(méi)有node再和它比較，也就不能在helper中判定它的次數(shù)是否最多还最，因此preMax墓阀，value，cnt和resList這些變量要成為全局變量拓轻。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<Integer> resList = new ArrayList<Integer>();
public int cnt = -1; //so for the first node, cnt != preMax; Must be global vriable, to suitble for last node
private int value = Integer.MAX_VALUE;
private int preMax = 0;
public int[] findMode(TreeNode root) {
helper(root);//Left tree
//check if last value should be added
if(cnt > preMax){
resList.clear();
resList.add(value);//add the Previous value
}else if(cnt == preMax){
resList.add(value);
}
int len = resList.size();
int[] out = new int[len];
for(int i =0 ;i< len; i++){
out[i] = resList.get(i);
}
return out;
}
private void helper(TreeNode node){
if(node == null) return;
helper(node.left);//Left tree
if(node.val != value){
if(cnt > preMax){
resList.clear();
resList.add(value);//add the Previous value
preMax = cnt;
}else if(cnt == preMax){
resList.add(value);//add the Previous value
}
value = node.val;
cnt = 1;//it must be the first new value
}else{
cnt++;
}
helper(node.right);//Right tree
}
}
