二叉搜索树中的众数
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
思路
初见思路是：直接把二叉树遍历一遍，得到结果数组，在用map进行频率统计，返回出现最多的那个即可
但是，像上面这样处理的话，统计频率那块的代码不太好写（需要自定义比较函数）
所以还是用 中序遍历+递归 的方式去做
不同的是，这里也要引入 二叉搜索树的最小绝对差 中的双指针的技巧
即在遍历过程中设置两个指针，一个指向前一节点，一个指向当前节点
在本题中，通过前一节点与当前节点的比较，来判断一个元素是否出现了多次，并统计其出现次数
这里还需要设置两个计数变量，一个count用来记录当前遍历值的出现次数，一个maxCount用于记录出现过的最大count。
当需要更新maxCount时，同时记录下当前的节点值并清空上次记录的节点值。
代码分析
还是先写递归函数
因为我们要遍历 整颗二叉树 ，且不需要立刻返回判断值，所以递归函数的输入参数是根节点且没有返回值。根据递归的中序遍历不难写出以下代码：
//定义计数变量
int maxCount = 0;
int count = 0;
//定义前一节点指针
TreeNode* pre = NULL;
void searchBST(TreeNode* cur){
//确定终止条件
if(cur == NULL) return;
//左
searchBST(cur->left);
//中，比较前一节点和当前节点并统计当前节点值的出现次数
//右
searchBST(cur->right);
return;//void也要写return
}
在 中 的处理逻辑里，我们引入双指针
一共有下面3中情况需要count去记录
- 前一节点指针为空时，当前节点指针指向第一个节点，因此count需要记1
- 前一节点指针不为空时，且当前节点指针值与前一节点值不相等，count需要记1（当前遍历值只出现了一次）
- 当前节点指针值与前一节点值相等，count需要累加记录
当记录完成，更新当前节点与前一节点的指针即可
//定义计数变量
int maxCount = 0;
int count = 0;
//定义前一节点指针
TreeNode* pre = NULL;
void searchBST(TreeNode* cur){
//左
searchBST(cur->left);
//中，比较前一节点和当前节点并统计当前节点值的出现次数
if(pre == NULL){//当前节点指针指向第一个节点
count = 1;
}else if(pre->val == cur->val){//当前节点指针值与前一节点值相等
count++;
}else{//前一节点指针不为空时，且当前节点指针值与前一节点值不相等
count = 1;
}
pre = cur;//更新当前节点与前一节点的指针
//右
searchBST(cur->right);
return;//void也要写return
}
得到count之后，我们需要去更新maxCount，也有两种情况：
- count与maxCount相同，说明有多个元素，它们都出现了多次并且次数相同（即多个众数的情况）
- count大于maxCount，说明有某个元素的出现次数更多，该元素将成为新的众数
情况一种我们只需将当前遍历的节点的值再加入结果数组即可
情况二则需要先清空之前结果数组保存的值，再加入新的众数（即当前遍历的节点的值）
上述过程也在 中 的处理逻辑里完成
//定义计数变量
int maxCount = 0;
int count = 0;
//定义前一节点指针
TreeNode* pre = NULL;
//定义结果数组
vector<int> res;
void searchBST(TreeNode* cur){
//左
searchBST(cur->left);
//中，比较前一节点和当前节点并统计当前节点值的出现次数
if(pre == NULL){//当前节点指针指向第一个节点
count = 1;
}else if(pre->val == cur->val){//当前节点指针值与前一节点值相等
count++;
}else{//前一节点指针不为空时，且当前节点指针值与前一节点值不相等
count = 1;
}
//比较并更新maxCount，记录结果值
if(count == maxCount){//出现多个众数
res.push_back(cur->val);
}else if(count > maxCount){//出现新的众数
//更新最大出现次数
maxCount = count;
//清空结果数组
res.clear();
//更新众数
res.push_back(cur->val);
}
pre = cur;
//右
searchBST(cur->right);
return;//void也要写return
}
完整代码
class Solution {
private:
//定义计数变量
int maxCount = 0;
int count = 0;
//定义前一节点指针
TreeNode* pre = NULL;
//定义结果数组
vector<int> res;
void searchBST(TreeNode* cur){
//确定终止条件
if(cur == NULL) return;
//左
searchBST(cur->left);
//中，比较前一节点和当前节点并统计当前节点值的出现次数
if(pre == NULL){//当前节点指针指向第一个节点
count = 1;
}else if(pre->val == cur->val){//当前节点指针值与前一节点值相等
count++;
}else{//前一节点指针不为空时，且当前节点指针值与前一节点值不相等
count = 1;
}
pre = cur;
//比较并更新maxCount，记录结果值
if(count == maxCount){//出现多个众数
res.push_back(cur->val);
}else if(count > maxCount){//出现新的众数
//更新最大出现次数
maxCount = count;
//清空结果数组
res.clear();
//更新众数
res.push_back(cur->val);
}
//右
searchBST(cur->right);
return;//void也要写return
}
public:
vector<int> findMode(TreeNode* root) {
//res.clear();//清理一下结果数组
searchBST(root);//调用递归
return res;//返回结果数组
}
};