本文主要是介绍Day52 代码随想录打卡|二叉树篇---二叉搜索树中的众数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目(leecode T501):
给你一个含重复值的二叉搜索树(BST)的根节点 root
,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
方法:本题要求二叉搜索树中的众数,我们还是要记住二叉搜索树的性质,中序遍历是一个递增有序的数组。因此本题我们可以理解为在一个递增有序的数组中求众数,这就好求很多了。因为递增有序的数组中相等的数肯定会是相邻出现的。因此我们只需要比较相邻的元素即可。同样使用递归法,分析三要素。
1:传入参数与返回值:传入的是树节点的指针,返回值为空,因为我们只需要对结果数组直接操作最后读取数组即可。
2:终止条件:终止条件是遇到空节点。
3:单层处理逻辑:每一层处理中,我们都要将当前节点值与前一个结点值做比较,如果相等就增加该值的count频率,如果某个值的频率为最大的频率,就将该值加入result数组中。因为我们是实时判断频率,因此可能会出现频率更大的值,我们只需要将该频率重新赋值为最新的最大频率,并清空结果数组将新的值加进去即可。
题解:
class Solution {
private:int count = 0;int maxCount = 0;TreeNode* pre = NULL;vector<int> result;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;if (count == maxCount) { // 如果和最大值相同,放进result中result.push_back(cur->val);}if(count > maxCount){maxCount = count;result.clear();result.push_back(cur->val);}searchBST(cur->right); //右return;}
public:vector<int> findMode(TreeNode* root) {count = 0;maxCount = 0;pre = NULL; // 记录前一个节点result.clear();searchBST(root);return result;}
};
这篇关于Day52 代码随想录打卡|二叉树篇---二叉搜索树中的众数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!