[二叉树]501. Find Mode in Binary Se

题目：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).

一个二叉搜索树，返回出现最多次数的value。
第一个想法是用HashMap，既可以查重，又可以计算次数，然而不符合follow up不用额外空间的要求，也没有利用到二叉搜索树的性质。

那么就是迭代了。对二叉搜索树，使用中序遍历可以完成值从小到大的遍历。这样相同的value必然连在一起，遇到一个不同于之前 value的node，就可以比较上一个value是否是最多次的value。

但是这题的陷阱和要注意的点非常多！

1.可能出现有多个次数相同的value的情况，但不知道会有几个，所以先用list暂存。
比如这样的情况：[1,1,2,null,null,null,2]
2.最后一个value的次数判断要回到主函数，因为后续没有node再和它比较，也就不能在helper中判定它的次数是否最多，因此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
    }
}