501. 二叉搜索树中的众数

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

假定 BST 有如下定义：

• 结点左子树中所含结点的值小于等于当前结点的值
• 结点右子树中所含结点的值大于等于当前结点的值
• 左子树和右子树都是二叉搜索树

例如： 给定 BST [1,null,2,2],

   1
    \
     2
    /
   2

返回[2].

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

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

思路

1. 最简单的方法就是遍历维护每个节点值和数量，最后取出最大的即可。
2. 遇到二叉搜索树第一个想到的点就是中序遍历升序。所以相等的数一定在中序遍历时相邻。遍历的时候维护一个最大频率，遇到最大频率的值就放入数组。如果遇到更大频率的值则清空目标数组再重新放入。

解法

class Solution {
    public TreeNode preNode;
    public int count = 1;
    public int maxCount = 1;
    public List<Integer> resList = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        if (root == null) {
            return null;
        }
        traversal(root);
        int[] result = new int[resList.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = resList.get(i);
        }
        return result;
    }

    public void traversal(TreeNode root) {
        if (root == null) {
            return;
        }
        traversal(root.left);
        if (preNode != null) {
            if (root.val == preNode.val) {
                count++;
            } else {
                count = 1;
            }
        }
        if (count == maxCount) {
            resList.add(root.val);
        } else if (count > maxCount) {
            maxCount = count;
            resList.clear();
            resList.add(root.val);
        }
        preNode = root;
        traversal(root.right);
    }
}