501. 二叉搜索树中的众数

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值

结点右子树中所含结点的值大于等于当前结点的值

左子树和右子树都是二叉搜索树

例如：

给定 BST [1,null,2,2],

   1

    \

     2

    /

   2

返回[2].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

PS：

遍历

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

      int preVal = 0, curTimes = 0, maxTimes = 0;

    ArrayList<Integer> list = new ArrayList<Integer>();

    public int[] findMode(TreeNode root) {

	traversal(root);

	int size = list.size();

	int[] ans = new int[size];

	for(int i = 0; i < size; i++){

	    ans[i] = list.get(i);

	}

	return ans;

    }

    //二叉搜索树中序遍历是递增顺序

    public void traversal(TreeNode root){

	if(root != null){

	    traversal(root.left);

	    //判断当前值与上一个值的关系, 更新 curTimes 和 preVal

	    if(preVal == root.val){

		curTimes++;

	    }else{

		preVal = root.val;

		curTimes = 1;

	    }

	    //判断当前数量与最大数量的关系, 更新 list 和 maxTimes

	    if(curTimes == maxTimes){

		list.add(root.val);

	    }else if(curTimes > maxTimes){

		list.clear();

		list.add(root.val);

		maxTimes = curTimes;

	    }

	    traversal(root.right);

	}

    }

}