leetcode 501.二叉搜索树中的众数

问题描述

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

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

假定 BST 满足如下定义：

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

示例 1：

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

示例 2：

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

提示：

树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

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

中序遍历

核心思路

如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。

不过对于搜索树，中序遍历是有序的。遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。

顺序扫描中序遍历序列，用 $\textit{base}$ 记录当前的数字，用 $\textit{count}$ 记录当前数字重复的次数，用 $\textit{maxCount}$ 来维护已经扫描过的数当中出现最多的那个数字的出现次数，用 $\textit{answer}$ 数组记录出现的众数。每次扫描到一个新的元素：

首先更新 $\textit{base}$ 和 $\textit{count}$ :
如果该元素和 $\textit{base}$ 相等，那么 $\textit{count}$ 自增 1；
否则将 $\textit{base}$ 更新为当前数字， $\textit{count}$ 复位为 1。
然后更新 $\textit{maxCount}$ ：
如果 $\textit{count} = maxCount$ ，那么说明当前的这个数字（ $\textit{base}$ ）出现的次数等于当前众数出现的次数，将 $\textit{base}$ 加入 $\textit{answer}$ 数组；

如果 $\textit{count} > maxCount$ ，那么说明当前的这个数字（ $\textit{base}$ ）出现的次数大于当前众数出现的次数，因此，我们需要将 $\textit{maxCount}$ 更新为 $\textit{count}$ ，清空 $\textit{answer}$ 数组后将 $\textit{base}$ 加入 $\textit{answer}$ 数组。
我们可以把这个过程写成一个 $\text{update}$ 函数。这样我们在寻找出现次数最多的数字的时候就可以省去一个哈希表带来的空间消耗。

然后，我们考虑不存储这个中序遍历序列。如果我们在递归进行中序遍历的过程中，访问当了某个点的时候直接使用上面的 $\text{update}$ 函数，就可以省去中序遍历序列的空间，代码如下。

code

class Solution {
public:
    vector<int> answer;
    int base, count, maxCount;

    void update(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.push_back(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer = vector<int> {base};
        }
    }

    void dfs(TreeNode* o) {
        if (!o) {
            return;
        }
        dfs(o->left);
        update(o->val);
        dfs(o->right);
    }

    vector<int> findMode(TreeNode* root) {
        dfs(root);
        return answer;
    }
};

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

Morris 中序遍历

核心思路

用 Morris 中序遍历的方法把中序遍历的空间复杂度优化到 $O(1)$ 。我们在中序遍历的时候，一定先遍历左子树，然后遍历当前节点，最后遍历右子树。在常规方法中，我们用递归回溯或者是栈来保证遍历完左子树可以再回到当前节点，但这需要我们付出额外的空间代价。我们需要用一种巧妙地方法可以在 $O(1)$ 的空间下，遍历完左子树可以再回到当前节点。我们希望当前的节点在遍历完当前点的前驱之后被遍历，我们可以考虑修改它的前驱节点的 $\textit{right}$ 指针。当前节点的前驱节点的 $\textit{right}$ 指针可能本来就指向当前节点（前驱是当前节点的父节点），也可能是当前节点左子树最右下的节点。如果是后者，我们希望遍历完这个前驱节点之后再回到当前节点，可以将它的 $\textit{right}$ 指针指向当前节点。

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

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

code

class Solution {
public:
    int base, count, maxCount;
    vector<int> answer;

    void update(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.push_back(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer = vector<int> {base};
        }
    }

    vector<int> findMode(TreeNode* root) {
        TreeNode *cur = root, *pre = nullptr;
        while (cur) {
            if (!cur->left) {
                update(cur->val);
                cur = cur->right;
                continue;
            }
            pre = cur->left;
            while (pre->right && pre->right != cur) {
                pre = pre->right;
            }
            if (!pre->right) {
                pre->right = cur;
                cur = cur->left;
            } else {
                pre->right = nullptr;
                update(cur->val);
                cur = cur->right;
            }
        }
        return answer;
    }
};