【Leetcode笔记】501.二叉搜索树中的众数

server/2024/12/22 20:42:56/

文章目录

  • 题目要求
  • ACM 模式代码
  • 知识点

题目要求

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。

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

假定 BST 满足如下定义:

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树
    在这里插入图片描述

虽然题目对于BST的定义已经违背常识  ̄へ ̄,但依据题意扩展解题思路是有意义的。
其次就是只要求出现频次最高的至少一个元素。

ACM 模式代码

#include <iostream>
#include <vector>
using namespace std;
#include <unordered_map>
#include <algorithm>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:void searchBST(TreeNode* cur, unordered_map<int, int>& map){if(cur == NULL) return;map[cur->val]++;searchBST(cur->left, map);searchBST(cur->right, map);}static bool cmp(const pair<int, int>& a, const pair<int, int>& b){return a.second > b.second; // 降序排列}
public:vector<int> findMode(TreeNode* root) {unordered_map<int, int> map;vector<int> result;if(root == NULL) return result;searchBST(root, map);vector<pair<int, int>> vec(map.begin(), map.end());sort(vec.begin(), vec.end(), cmp); // 按照频率进行降序排列,每个对儿的第一个值是元素result.push_back(vec[0].first);for(int i = 1; i < vec.size(); i++){if(vec[i].second == vec[0].second){result.push_back(vec[i].first);}else{break;}}return result;}
};int main(void)
{TreeNode* root = new TreeNode(1);root->right = new TreeNode(2);root->right->left = new TreeNode(2);Solution solution;vector<int> res = solution.findMode(root);for(int i = 0; i < res.size(); i++){cout << res[i] << endl;}return 0;   
}

知识点

  1. cmp函数必须声明为静态成员函数
    这是因为 sort() 函数为 STL 中的一个全局算法,并不依赖于任何类的特定实例;而sort想调用cmp函数就必须要保证cmp函数也是一个静态成员函数。
    也就是说,我们想使用Solution类里的findMode()函数,就必须通过这样的方式:
    Solution solution;vector<int> res = solution.findMode(root);

而全局范围定义的函数就可以不用创建类的实例而直接调用,sort(vec.begin(), vec.end(), cmp);.
2. cmp 函数的输入参数需要 const 修饰

    static bool cmp(const pair<int, int>& a, const pair<int, int>& b){return a.second > b.second; // 降序排列}

首先,传入的是 a 和 b 的引用,这样可以提高效率,避免复制操作产生临时变量;另外,因为在排序过程中,sort函数会频繁地访问这些参数,通过将参数声明为const,可以保证这些参数在函数执行过程中不会被修改,增强安全性和可读性。


http://www.ppmy.cn/server/8633.html

相关文章

IDEA报错然后pycharm闪退

pycharm闪退&#xff0c;在C盘的USER文件夹下有报错文件 打开一看&#xff0c;说内存不足 # There is insufficient memory for the Java Runtime Environment to continue. # Native memory allocation (mmap) failed to map 14596177920 bytes for G1 virtual space # Possib…

2024年高校辅导员考试题库及答案

一、选择题 4.根据宪法和法律&#xff0c;可以制定行政法规的是&#xff1a;&#xff08;&#xff09; A.全国人民代表大会&#xff1b; B.全国人民代表大会常务委员会&#xff1b; C.国务院&#xff1b; D.国家教育部 答案&#xff1a;C …

os模块学习

【一】文件路径相关的操作 【1】获取当前文件所在的文件夹路径 # os.path.dirname(__file__) ​ import os file_name os.path.dirname(__file__) print(file_name) # H:\pycharm projects\day\模块学习2 【2】获取当前文件所在的文件路径 # os.path.abspath(__fil…

计算机网络实验实验之VLAN的配置与分析

实验目的 了解什么是带内管理&#xff1b;熟练掌握如何使用telnet方式管理交换机&#xff1b;熟练掌握如何为交换机设置web方式管理&#xff1b;熟练掌握如何进入交换机web管理方式&#xff1b;了解交换机web配置界面&#xff0c;并能进行部分操作。 (6)了解VLAN原理&#xf…

Springboot的@Cacheable注解

概述 Cacheable 是 Spring 框架提供的一种基于缓存的注解&#xff0c;它可以被应用在方法上以指示该方法的结果需要被缓存起来&#xff0c;缓存在哪个 Cache 中以及该方法使用何种缓存键。 使用 Cacheable 注解后&#xff0c;每次调用该方法时&#xff0c;首先从缓存中检查是…

嘴尚绝卤味:传统与现代的完美结合

卤味&#xff0c;作为中国传统美食中的一大类&#xff0c;凭借其独特的口感和丰富的风味&#xff0c;一直深受食客们的喜爱。而在众多卤味品牌中&#xff0c;嘴尚绝卤味凭借其卓越的品质和创新的口味&#xff0c;成为了市场上的佼佼者。今天&#xff0c;就让我们一起来品味嘴尚…

HCIP的学习(8)

OSPF数据报文 OSPF头部信息&#xff08;公共固定&#xff09; 版本&#xff1a;OSPF版本&#xff0c;在IPv4网络中版本字段恒定为数值2&#xff08;v1属于实验室版本&#xff0c;v3属于IPv6&#xff09;类型&#xff1a;代表具体是哪一种报文&#xff0c;按照1~5排序&#xff…

Leetcode 第 394 场周赛

Leetcode 第 394 场周赛 1. [统计特殊字母的数量 I](https://leetcode.cn/problems/count-the-number-of-special-characters-i/)2. [统计特殊字母的数量 II](https://leetcode.cn/problems/count-the-number-of-special-characters-ii/)3. [使矩阵满足条件的最少操作次数](htt…