24.二叉搜索树中的众数

题目描述

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

BST定义如下：

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

解题思路

中序遍历

首先明确一个概念，一棵BST的中序遍历序列是一个非递减的有序序列。而且重复出现的数字一定是连续出现的。所以，我们可以顺序扫描中序遍历序列，用 base记录当前的数字，用count记录当前数字重复的次数，用maxCount来维护已经扫描过的数当中出现最多的那个数字的出现次数，用answer数组记录出现的众数。每次扫描到一个新的元素：

• 首先更新base和count：
  • 如果该元素和base相等，那么count自增1
  • 否则将base更新为当前数字，count复位为1
• 然后更新maxCount：
  • 如果count = maxCount，那么说明当前的这个数字（base）出现的次数等于当前众数出现的次数，将base加入answer数组
  • 如果count > maxCount，那么说明当前的这个数字（base）出现的次数大于当前众数出现的次数，因此，将maxCount更新为count，清空answer数组后将base加入answer数组

将上述操作封装成一个函数，剩下的就是解决中序遍历的问题。

普通的中序遍历，空间复杂度为O(n),而Morris中序遍历可以把空间复杂度优化到O(1)。

Morris中序遍历可以在遍历完左子树之后回到当前节点。我们希望当前的节点在遍历完当前点的前驱之后被遍历，我们可以考虑修改它的前驱结点的right指针。当前节点的前驱结点的right指针可能本来就指向当前节点（前驱是当前节点的父节点），也可能是当前节点左子树最右下的节点。如果是后者，我们希望遍历完这个前驱结点之后再回到当前节点，可以将它的right指针指向当前节点。

Morris中序遍历的一个重要步骤就是寻找当前节点的前驱节点，并且Morris中序遍历寻找下一个点始终是通过转移到right指针指向的位置来完成的。

• 如果当前节点没有左子树，则遍历这个点，然后跳转到当前节点的右子树。
• 如果当前节点有左子树，那么它的前驱节点一定在左子树上，我们可以在左子树上一直向右走，找到当前点的前驱节点。
  • 如果前驱节点没有右子树，就将前驱结点的right指针指向当前节点。这一步是为了在遍历完前驱节点后能找到前驱节点的后继，也就是当前节点。
  • 如果前驱节点的右子树为当前节点，说明前驱节点已经被遍历过并被修改了right指针，这个时候我们重新将前驱的右孩子设置为空，遍历当前的点，然后跳转到当前节点的右子树。

Code：

class Solution{
    int base,count,maxCount;
    List<Integer> ans = new ArrayList<>();

    public int[] findMode(TreeNode root){
        TreeNode cur = root,pre = null;
        while(cur != null){
            if(cur.left == null){
                update(cur.val);
                cur = cur.right;
                continue;
            }
            pre = cur.left;
            while(pre.right != null && pre.right != cur){
                pre = pre.right;
            }
            if(pre.right == null){
                pre.right = cur;
                cur = cur.left;
            }else{
                pre.right = null;
                update(cur.val);
                cur = cur.right;
            }
        }
        int[] res = new int[ans.size()];
        for(int i = 0;i < ans.size();i++){
            res[i] = ans.get(i);
        }
        return res;
    }
    public void update(int x){
        if(x == base){
            count++;
        }else{
            count = 1;
            base = x;
        }
        if(count == maxCount){
            ans.add(base);
        }
        if(count > maxCount){
            maxCount = count;
            ans.clear();
            ans.add(base);
        }
    }
}