题目描述
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2]
输出：[2]示例 2：
输入：root = [0]
输出：[0]提示：
- 树中节点的数目在范围
[1, 10^4]内 -10^5 <= Node.val <= 10^5
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
思路
使用双指针遍历二叉树搜索树，统计元素出现频率，如果频率count等于maxCount（最大频率），把这个元素加入到结果集中；如果频率count大于maxCount，不仅要更新maxCount，而且要清空结果集。
代码
C++版：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 递归法，中序遍历
int maxCount = 0; // 最大频率
int count = 0; // 统计频率
TreeNode* pre = NULL;
vector<int> result;
void traversal(TreeNode * cur){
if(cur==NULL) return;
traversal(cur->left); // 左
if(pre==NULL) count+=1;
else if(pre->val==cur->val){ // 与前一个节点数值相同
count++;
}
else{ // 与前一个节点数值不同
count=1;
}
if(count>maxCount){ // 如果计数大于最大值频率
maxCount=count; // 更新最大频率
result.clear(); // 不要忘记清空result，之前result里的元素都失效了
result.push_back(cur->val);
}
else if(count==maxCount){ // 如果和最大值相同，放进result中
result.push_back(cur->val);
}
pre=cur; // 更新上一个节点
traversal(cur->right); // 右
return ;
}
vector<int> findMode(TreeNode* root) {
traversal(root);
return result;
}
};Python版：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.maxCount = 0 # 最大频率
self.count = 0 # 统计频率
self.pre = None
self.result = []
def searchBST(self, cur):
if cur is None:
return
self.searchBST(cur.left) # 左
# 中
if self.pre is None: # 第一个节点
self.count = 1
elif self.pre.val == cur.val: # 与前一个节点数值相同
self.count += 1
else: # 与前一个节点数值不同
self.count = 1
self.pre = cur # 更新上一个节点
if self.count == self.maxCount: # 如果与最大值频率相同，放进result中
self.result.append(cur.val)
if self.count > self.maxCount: # 如果计数大于最大值频率
self.maxCount = self.count # 更新最大频率
self.result = [cur.val] # 不要忘记清空result，之前result里的元素都失效了
self.searchBST(cur.right) # 右
return
def findMode(self, root: Optional[TreeNode]) -> List[int]:
self.searchBST(root)
return self.result需要注意的地方
1.二叉搜索树的相关题目，常用中序遍历。
2.如果本题不是二叉搜索树，可以把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。
3.本题有一个技巧：适时清空结果集。