501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

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

示例 1：

img.png

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

• 树中节点的数目在范围 [1, 10^4] 内
• -10^5 <= Node.val <= 10^5

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

中序遍历+贪心

在中序位置更新众数及其次数。

之所以用中序，是因为二叉搜索树的中序遍历是有序的，所以重复的数字会在一起。所以只需要变量记录当前数字即可， 如果遇到新数字，则更新变量，因为后面不可能出现前面的数字了，所以直接更新即可。 如果无序，则后面也可能出现前面的数字，所以不能舍弃历史数据，所以要用数组或哈希表这种具有记忆能力的数据结构。

class Solution {
    List<Integer> answer = new ArrayList<>(); // 存储众数的列表
    int base, count, maxCount; // base 表示当前值，count 表示当前值的出现次数，maxCount 表示众数的出现次数

    public int[] findMode(TreeNode root) {
        dfs(root); // 深度优先搜索遍历树
        
        int[] mode = new int[answer.size()]; // 将结果从列表转换为数组
        for (int i = 0; i < answer.size(); ++i) {
            mode[i] = answer.get(i);
        }
        return mode; // 返回众数数组
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return; // 如果节点为空，返回
        }
        dfs(node.left); // 递归遍历左子树
        update(node.val); // 更新当前值的出现次数。当处理当前值时，我们已经把左子树的节点的出现次数更新过了。
        dfs(node.right); // 递归遍历右子树
    }

    public void update(int x) {
        // base默认是0，count默认是0
        if (x == base) { // base其实是前一个数，count是这个数连续出现的次数，注意是连续，在中序遍历中，相同的数一定连续出现。
            ++count; // 如果当前值与 base 相同，增加出现次数
        } else {
            count = 1; // 如果当前值与 base 不同，说明遇到了新数，重置出现次数为 1
            base = x; // 更新 base 为当前值。重点。
        }
        
        // 计算完次数后，检查该次数是不是当前最大值。
        if (count == maxCount) {
            answer.add(base); // 如果当前值的出现次数等于最大出现次数，将其加入众数列表
        }
        if (count > maxCount) {
            maxCount = count; // 如果当前值的出现次数超过最大出现次数，更新最大出现次数
            answer.clear(); // 清空众数列表。重点。
            answer.add(base); // 将当前值加入众数列表
        }
    }
}

• 时间复杂度：O(n)。即遍历这棵树的复杂度。
• 空间复杂度：O(n)。即递归的栈空间的空间代价。

Morris中序遍历

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

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

class Solution {
    int base, count, maxCount; // base 表示当前值，count 表示当前值的出现次数，maxCount 表示众数的出现次数
    List<Integer> answer = new ArrayList<>(); // 存储众数的列表

    /**
     * 查找二叉搜索树中的众数
     *
     * @param root 二叉搜索树的根节点
     * @return 众数数组
     */
    public int[] findMode(TreeNode root) {
        TreeNode cur = root, pre = null; // cur 表示当前节点，pre 表示当前节点的前驱节点
        
        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[] mode = new int[answer.size()]; // 将结果从列表转换为数组
        for (int i = 0; i < answer.size(); ++i) {
            mode[i] = answer.get(i);
        }
        return mode; // 返回众数数组
    }

    /**
     * 更新当前值的出现次数，并检查是否需要更新众数列表
     *
     * @param x 当前节点的值
     */
    public void update(int x) {
        if (x == base) {
            ++count; // 如果当前值与 base 相同，增加出现次数
        } else {
            count = 1; // 如果当前值与 base 不同，重置出现次数为 1
            base = x; // 更新 base 为当前值
        }
        if (count == maxCount) {
            answer.add(base); // 如果当前值的出现次数等于最大出现次数，将其加入众数列表
        }
        if (count > maxCount) {
            maxCount = count; // 如果当前值的出现次数超过最大出现次数，更新最大出现次数
            answer.clear(); // 清空众数列表
            answer.add(base); // 将当前值加入众数列表
        }
    }
}

• 时间复杂度：O(n)。每个点被访问的次数不会超过两次，故这里的时间复杂度是 O(n)。
• 空间复杂度：O(1)。使用临时空间的大小和输入规模无关。