题目描述

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

假定 BST 有如下定义：

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

样例

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

   1
    \
     2
    /
   2
返回[2].

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

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

算法1

时间复杂度 $O(n)$

根据二叉搜索树性质，采用中序遍历更新结果。

记录三个变量信息：当前节点的值val；当前节点值出现的次数cnt; 同一值最多出现的次数maxCnt。

遍历到当前节点cur时，比较cur.val与当前记录的val是否相等：
（1）若相等，则对应记录的cnt+1；
（2）若不相等，则更新cnt为1，val为cur.val；

将当前记录的cnt与记录的maxCnt进行比较：
（1）若cnt==maxCnt，则向结果集中加入当前val;
（2）若cnt>maxCnt，则删除原结果集中所有元素，加入当前val

每个节点被遍历一遍，时间复杂度$O(n)$，采用莫里斯中序遍历，空间复杂度$O(1)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int cnt = 0,val = 0,maxCnt = 0;
    List<Integer> res=new ArrayList<>();
    public int[] findMode(TreeNode root) {
        TreeNode cur = root;
        while (cur != null){
            if (cur.left == null){
                calc(cur.val);
                cur = cur.right;
            }else {
                TreeNode p = cur.left;
                while (p.right != null && p.right !=cur)
                    p = p.right;
                if (p.right == null){
                    p.right = cur;
                    cur = cur.left;
                }else {
                    p.right = null;
                    calc(cur.val);
                    cur = cur.right;
                }
            }
        }
        int[] ans =new int[res.size()];
        for (int i = 0; i < ans.length; i ++)
            ans[i] = res.get(i);

        return ans;
    }

    public void calc(int x){
        if (x == val)
            cnt ++;
        else {
            val = x;
            cnt = 1;
        }
        if (cnt == maxCnt)
            res.add(val);
        if (cnt > maxCnt){
            maxCnt = cnt;
            res.clear();
            res.add(val);
        }
    }

}