题目
给定一个BST二分查找树，求众数。
要求，除去递归的空间占用，其他代码空间复杂度为O(1)。
分析
很显然，二分查找树的中序遍历就是一个有序数组。
有序数组查找最长的连续重复的数字，就是众数了。需要注意的是，题目要求返回重复的数字。另外，空间复杂度必须为O(1)。要写出这样的代码并不困难。
运行16ms，击败62%
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
vector<int> mode;
int last;
int lastCount;
int modeCount;
public:
vector<int> findMode(TreeNode* root) {
last = 0;
lastCount = 0;
modeCount = 0;
mode.clear();
runMode(root);
return mode;
}
void runMode(TreeNode* root){
if(root != NULL){
runMode(root -> left);
int nowValue = root->val;
int nowCount = nowValue != last? 1 : lastCount + 1;
if(modeCount == nowCount){
mode.push_back(nowValue);
}
if(modeCount < nowCount){
modeCount = nowCount;
mode.clear();
mode.push_back(nowValue);
}
last = nowValue;
lastCount = nowCount;
runMode(root -> right);
}
}
};
