给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2]
输出：[2]
示例 2：
输入：root = [0]
输出：[0]
提示：
- 树中节点的数目在范围
[1, 10^4]内 -10^5 <= Node.val <= 10^5
进阶： 你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
首先一定能想到一个最朴素的做法：因为这棵树的中序遍历是一个有序的序列，所以可以先获得这棵树的中序遍历，然后从扫描这个中序遍历序列，然后用一个哈希表来统计每个数字出现的个数，这样就可以找到出现次数最多的数字。但是这样做的空间复杂度显然不是 O ( 1 ) O(1) O(1) 的，原因是哈希表和保存中序遍历序列的空间代价都是 O ( n ) O(n) O(n) 。
解法1 O ( 1 ) O(1) O(1) 空间遍历，但仍有递归调用开销
首先，我们考虑在寻找出现次数最多的数时，不使用哈希表。 这个优化是基于二叉搜索树中序遍历的性质：一棵二叉搜索树的中序遍历序列是一个非递减的有序序列。例如：
1
/ \
0 2
/ \ /
-1 0 2
这样一颗二叉搜索树的中序遍历序列是 { − 1 , 0 , 0 , 1 , 2 , 2 } \{ -1, 0, 0, 1, 2, 2 \} {−1,0,0,1,2,2} 。
可以发现，例如这里的 0 0 0 和 2 2 2 ，它们都重复出现了，并且所有的 0 0 0 都集中在一个连续的段内，所有的 2 2 2 也集中在一个连续的段内。顺序扫描中序遍历序列，用 b a s e base base 记录当前的数字，用 count \textit{count} count 记录当前数字重复的次数，用 m a x C o u n t maxCount maxCount 来维护已经扫描过的数当中出现最多的那个数字的出现次数，用 a n s w e r answer answer 数组记录出现的众数。每次扫描到一个新的元素：
- 首先更新 base \textit{base} base 和 c o u n t count count ：
- 如果该元素和 b a s e base base 相等，那么 c o u n t count count 自增 1 1 1 ；
- 否则将 b a s e base base 更新为当前数字， count \textit{count} count 复位为 1 1 1 。
- 然后更新 m a x C o u n t maxCount maxCount ：
- 如果 c o u n t = m a x C o u n t count=maxCount count=maxCount ，那么说明当前的这个数字（ b a s e base base）出现的次数等于当前众数出现的次数，将 b a s e base base 加入 a n s w e r answer answer 数组；
- 如果 c o u n t > m a x C o u n t count>maxCount count>maxCount ，那么说明当前的这个数字（ b a s e base base 出现的次数大于当前众数出现的次数，因此，我们需要将 m a x C o u n t maxCount maxCount 更新为 count \textit{count} count ，清空 a n s w e r answer answer 数组后将 base \textit{base} base 加入 a n s w e r answer answer 数组。
把这个过程写成一个 u p d a t e update update 函数。这样在寻找出现次数最多的数字时，就可以省去一个哈希表带来的空间消耗。然后，我们考虑不存储这个中序遍历序列。 如果在递归进行中序遍历的过程中，访问当了某个点的时候直接使用上面的 update \text{update} update 函数，就可以省去中序遍历序列的空间，代码如下。
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* root) {
if (!root) return;
dfs(root->left);
update(root->val);
dfs(root->right);
}
vector<int> findMode(TreeNode* root) {
dfs(root);
return answer;
}
};
复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n) 。即遍历这棵树的复杂度。
- 空间复杂度： O ( n ) O(n) O(n) 。即递归的栈空间的空间代价。
解法2 M o r r i s Morris Morris 中序遍历
接着上面的思路，用 M o r r i s Morris Morris 中序遍历的方法把中序遍历的空间复杂度优化到 O ( 1 ) O(1) O(1) 。在中序遍历时，一定先遍历左子树，然后遍历当前节点，最后遍历右子树。在常规方法中，用递归回溯或者是栈来保证遍历完左子树可以再回到当前节点，但这需要付出额外的空间代价。。
我们希望当前的节点在遍历完当前点的前驱之后被遍历，考虑修改它的前驱节点的 right \textit{right} right 指针。当前节点的前驱节点的 r i g h t right right 指针可能本来就指向当前节点（前驱是当前节点的父节点），也可能是当前节点左子树最右下的节点。，可以将它的 right \textit{right} right 指针指向当前节点。
Morris 中序遍历的一个重要步骤就是寻找当前节点的前驱节点，并且 M o r r i s Morris Morris 中序遍历寻找下一个点始终是通过转移到 r i g h t right right 指针指向的位置来完成的。
- 如果当前节点没有左子树，则遍历这个点，然后跳转到当前节点的右子树。
- 如果当前节点有左子树，那么它的前驱节点一定在左子树上，我们可以在左子树上一直向右行走，找到当前点的前驱节点。
- 如果前驱节点没有右子树，就将前驱节点的 right \textit{right} right 指针指向当前节点。这一步是为了在遍历完前驱节点后能找到前驱节点的后继，也就是当前节点。
- 如果前驱节点的右子树为当前节点，说明前驱节点已经被遍历过并被修改了 right \textit{right} right 指针，这个时候我们重新将前驱的右孩子设置为空，遍历当前的点，然后跳转到当前节点的右子树。
因此我们可以得到这样的代码框架：
TreeNode *cur = root, *pre = nullptr;
while (cur) {
if (!cur->left) {
// 遍历cur
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;
// 遍历cur
cur = cur->right;
}
}
最后我们将 遍历 cur 替换成之前的 update \text{update} update 函数即可。
class Solution {
public:
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 }; }
}
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;
}
};
复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n) 。每个点被访问的次数不会超过两次，故这里的时间复杂度是 O ( n ) O(n) O(n) 。
- 空间复杂度： O ( 1 ) O(1) O(1) 。使用临时空间的大小和输入规模无关。