苏州建设交易中心网站,怎么制作网站记事本,软件开发培训机构哪家好,夏家胡同网站建设题目
501. 二叉搜索树中的众数
简单
相关标签 树 深度优先搜索 二叉搜索树 二叉树
给你一个含重复值的二叉搜索树#xff08;BST#xff09;的根节点 root #xff0c;找出并返回 BST 中的所有 众数#xff08;即#xff0c;出现频率最高的元素#xff09;。
…题目
501. 二叉搜索树中的众数
简单
相关标签 树 深度优先搜索 二叉搜索树 二叉树
给你一个含重复值的二叉搜索树BST的根节点 root 找出并返回 BST 中的所有 众数即出现频率最高的元素。
如果树中有不止一个众数可以按 任意顺序 返回。
假定 BST 满足如下定义
结点左子树中所含节点的值 小于等于 当前节点的值结点右子树中所含节点的值 大于等于 当前节点的值左子树和右子树都是二叉搜索树 示例 1 输入root [1,null,2,2]
输出[2]示例 2
输入root [0]
输出[0]提示
树中节点的数目在范围 [1, 104] 内-105 Node.val 105 进阶你可以不使用额外的空间吗假设由递归产生的隐式调用栈的开销不被计算在内
思路和解题方法一暴力 定义一个私有函数searchBST用于前序遍历二叉搜索树并统计每个元素的频率。函数参数包括当前节点指针cur和存储元素频率的unordered_mapmap。在searchBST函数中如果当前节点为空则直接返回否则对当前节点的值进行统计将当前节点的值作为map的键并将对应的值加1表示该元素出现的频率。递归调用searchBST函数传入当前节点的左子节点和map再传入当前节点的右子节点和map实现前序遍历。定义一个静态成员函数cmp用于比较两个pair类型的元素按照频率降序排列。在排序时使用此比较函数。在findMode函数中首先创建一个空的unordered_map类型的map用于存储元素及其频率。如果输入的根节点为空直接返回空的结果数组。调用searchBST函数传入根节点和map统计二叉搜索树中每个元素的频率。将map转化为vector类型并使用sort函数对vector进行排序排序方式为按照元素的频率降序排列。创建一个空的结果数组result将排序后的第一个元素的键也就是出现频率最高的元素添加到result中。遍历排序后的vector从第二个元素开始如果其频率和第一个元素的频率相同则将其键添加到result中否则结束遍历。返回结果数组result。 复杂度 时间复杂度: O(n logn) 时间复杂度 前序遍历二叉树的时间复杂度为 O(n)其中 n 是二叉树的节点数。构建哈希表的过程中对每个节点进行插入操作的平均时间复杂度为 O(1)。因此构建哈希表的时间复杂度也是 O(n)。对哈希表进行排序的时间复杂度为 O(nlogn)。综上所述算法的时间复杂度为 O(n) O(n) O(nlogn) O(nlogn)。 空间复杂度 O(n) 空间复杂度 使用了一个哈希表来存储元素及其频率哈希表的空间复杂度是 O(n)。将哈希表转换成了向量空间复杂度仍然是 O(n)。保存结果的向量最多可能存储所有节点的值因此空间复杂度也是 O(n)。综上所述算法的空间复杂度为 O(n)。 c 代码
class Solution {
private:// 前序遍历二叉搜索树统计每个元素的频率void searchBST(TreeNode* cur, unordered_mapint, int map) {if (cur NULL) return ;map[cur-val]; // 统计元素频率searchBST(cur-left, map); // 遍历左子树searchBST(cur-right, map); // 遍历右子树return ;}// 静态成员函数用于比较两个pair类型元素按照频率降序排列static bool cmp(const pairint, int a, const pairint, int b) {return a.second b.second;}
public:vectorint findMode(TreeNode* root) {unordered_mapint, int map; // 存储元素及其频率的mapkey为元素value为频率vectorint result; // 结果数组if (root NULL) return result; // 根节点为空直接返回空结果数组searchBST(root, map); // 统计二叉搜索树中每个元素的频率vectorpairint, int vec(map.begin(), map.end()); // 将map转换为vectorsort(vec.begin(), vec.end(), cmp); // 按照频率降序排列result.push_back(vec[0].first); // 将频率最高的元素添加到结果数组中for (int i 1; i vec.size(); i) {// 遍历排序后的vector如果元素频率与第一个元素的频率相同则添加到结果数组中否则结束遍历if (vec[i].second vec[0].second) result.push_back(vec[i].first);else break;}return result; // 返回结果数组}
};思路和解题方法二双指针 加 时时优化 使用了一个全局变量 maxCount 来记录最大频率使用 count 来统计当前节点值出现的频率。同时引入了一个 pre 变量来记录前一个访问的节点以便比较当前节点与前一个节点的值是否相同。函数 searchBST 是进行中序遍历的辅助函数通过递归遍历左子树、处理当前节点、递归遍历右子树的顺序进行搜索。在处理当前节点时首先判断当前节点值与前一个节点值是否相同若相同则将 count 增加 1否则将 count 重置为 1。然后根据 count 的大小与 maxCount 进行比较并更新 maxCount 和 result。如果 count 与 maxCount 相同说明当前节点值出现的频率与最大频率相同将其加入 result 中。如果 count 大于 maxCount则更新 maxCount 并清空 result将当前节点值放入 result 中。在 findMode 函数中初始化各个变量然后调用 searchBST 开始搜索并返回结果数组 result。 复杂度 时间复杂度: O(n) 时间复杂度是O(n)其中n是二叉搜索树中的节点数。因为我们需要遍历所有的节点来统计它们的频率。 空间复杂度 O(1) 不利用额外空间 c 代码
class Solution {
private:int maxCount 0; // 最大频率int count 0; // 统计频率TreeNode* pre NULL; // 前一个节点vectorint 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之前result中的元素都无效了result.push_back(cur-val);}searchBST(cur-right); // 右子树return ;}public:vectorint findMode(TreeNode* root) {count 0;maxCount 0;pre NULL; // 初始化前一个节点为空result.clear(); // 清空result向量searchBST(root); // 调用中序遍历函数搜索出现频率最高的节点值return result; // 返回结果向量}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
