题目
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],
1 \ 2 / 2
返回[2].
解题
方法一：中序遍历+暴力统计
先中序遍历，然后用dict统计每个元素的值出现频率，然后排序把高频出现的放在前面，最后把高频出现的值给取出来
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def findMode(self, root: TreeNode) -> List[int]: #中序遍历 if not root: return [] stack = [] res = [] cur = root while stack or cur: while cur: stack.append(cur) cur = cur.left cur = stack.pop() res.append(cur.val) cur = cur.right #统计频率 hush = {} for num in res: hush[num]=hush.get(num,0)+1 #排序（频率高的放前面） tmp = [] for key,freq in hush.items(): tmp.append((freq,key)) tmp.sort(reverse=True) # 取出频率高的 res = [] prev = None for freq,key in tmp: if not prev or prev==freq: res.append(key) prev = freq return res
c++解法
按出现频率排序，这题用到 直接排序的方法,也就是sort，并且自定义排序函数
leetcode-347：前 K 个高频元素此题中使用的是堆排序。
要能够掌握直接排序和堆排序.
class Solution { public: bool static cmp(const pair<int,int>& a,const pair<int,int>& b){ return a.second>b.second; } vector<int> findMode(TreeNode* root) { stack<TreeNode*> stack; TreeNode* cur=root; unordered_map<int,int> map; while(!stack.empty()||cur){ while(cur){ stack.push(cur); cur=cur->left; } cur=stack.top(); stack.pop(); map[cur->val]++; cur=cur->right; } vector<pair<int,int>> vec(map.begin(),map.end()); sort(vec.begin(),vec.end(),cmp); vector<int> res; res.push_back(vec[0].first); for(int i=1;i<vec.size();i++){ if(vec[i].second==vec[0].second) res.push_back(vec[i].first); else break; } return res; } };
java解法
class Solution { public int[] findMode(TreeNode root) { if(root==null) return new int[]{}; Map<Integer,Integer> mp=new HashMap<>(); //遍历树 Queue<TreeNode> q=new LinkedList<>(); q.add(root); while(!q.isEmpty()){ TreeNode cur=q.poll(); mp.put(cur.val,mp.getOrDefault(cur.val,0)+1); if(cur.left!=null){ q.add(cur.left); } if(cur.right!=null){ q.add(cur.right); } } //找到高频元素 //创建大顶堆 PriorityQueue<Integer> pq=new PriorityQueue<>(new Comparator<Integer>(){ public int compare(Integer a,Integer b){ if(mp.get(a)>mp.get(b)) return -1; else return 1; } }); for(Integer key:mp.keySet()){ pq.add(key); } List<Integer> res=new ArrayList<>(); res.add(pq.poll()); int k=mp.get(res.get(0)); while(!pq.isEmpty()&&mp.get(pq.peek())==k){ res.add(pq.poll()); } int[] ans=new int[res.size()]; for(int i=0;i<res.size();i++){ ans[i]=res.get(i); } return ans; } }
