LeetCode 501： 二叉搜索树中的众数 | C++语言版

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

题目描述

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

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

假定 BST 满足如下定义：

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

解题思路

思路一：使用迭代

代码实现

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 {
private:// 最大频率int maxCount=0;// 统计频率int count=0;//前一节点TreeNode* pre=NULL;//结果集vector<int> result;void searchBST(TreeNode* cur){if(cur==NULL) return;//左searchBST(cur->left);//中// 第一个节点 频率为1if(pre==NULL) count=1;// 当前节点cur与前一个节点pre数值相同 频率加1else if(pre->val==cur->val) count++;// 数值不同 频率不变else count=1;// 更新上一个节点pre=cur;//当前元素频率count 等于最大频率 maxCount，把这个元素直接加入结果集中if(count==maxCount){result.push_back(cur->val);}//当前元素频率count 大于最大频率 maxCountif(count>maxCount){// 更新最大频率maxCount=count;//清空结果集result.clear();//把这个元素加入到结果集中result.push_back(cur->val);}//右searchBST(cur->right);return;}public:vector<int> findMode(TreeNode* root) {//二叉搜索树（BST）:使用中序遍历进行有序遍历（左中右）//遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较,然后就把出现频率最高的元素输出就可以了。在树中就使用指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较//求最大频率的元素集合（多个众数）：先遍历一遍数组，找出最大频率（maxCount），当前元素频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集，最后把这个元素加入到结果集中count=0;maxCount=0;TreeNode* pre=NULL;result.clear();searchBST(root);return result;}
};

运行结果

参考文章：

https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html#%E9%80%92%E5%BD%92%E6%B3%95

思路二：减少遍历节点数

代码实现

C++

在这里插入代码片

运行结果

参考文章：