算法-二叉树篇20-二叉搜索树中的众数

二叉搜索树中的众数

力扣题目链接

题目描述

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

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

假定 BST 满足如下定义：

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

解题思路

这道题其实可以直接中序遍历然后结合数组找出众数即可，我是利用前k个高频元素来做，麻烦一些，但是可扩展性高，同时复习一下unorder_map，sort等用法，过了几天有点忘记了。 详细思路可以看我之前的文章：算法-栈和队列篇05-前 K 个高频元素

题解 class Solution { public: static bool cmp(pair<int, int> x, pair<int, int> y){ return x.second > y.second; } vector<int> findMode(TreeNode* root) { vector<int> ans; if(!root){ return ans; } unordered_map<int, int> um;// 存储节点值和出现次数 stack<TreeNode*> st; TreeNode* cur = root; while(!st.empty() || cur != NULL){ if(cur != NULL){ st.push(cur); cur = cur->left; } else{ cur = st.top(); st.pop(); um[cur->val]++; cur = cur->right; } } // 对map排序，排序规则为按照出现次数 vector<pair<int, int>> arr(um.begin(), um.end()); sort(arr.begin(), arr.end(), cmp); // 最大的先放入答案数组中 ans.push_back(arr[0].first); for(int i = 1; i < arr.size(); i++){ // 循环判断前几个的出现次数是否相等，相等就加上 if(arr[i].second == arr[i - 1].second){ ans.push_back(arr[i].first); } else { break; } } return ans; } };