赞
踩
Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.
Assume a BST is defined as follows:
For example:
Given BST [1,null,2,2]
,
1 \ 2 / 2
return [2]
.
Note: If a tree has more than one mode, you can return them in any order.
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
思路:
这道题如果允许用O(n)的空间复杂度就容易很多,可以用哈希表来做节点值(key),节点值出现的次数(value),最后在哈希表中寻找value最大的key即是答案。
为了实现O(1)的空间复杂度,且考虑到是二叉搜索树,所以采用中序遍历便可以得到由小到大的排序,存储pre上一个节点的值,如果pre不为空(非首节点)则通过cur统计连续出现相同数字的次数,如果次数等于max(历史出现最大数字对应的次数),数字就放到res中,大于max就说明找到了更大的数字对应的数字,则把res清空,数字放入res中,更新max。
这道题要注意的细节很多,初始化时cur为1,不能为0,因为考虑到头结点的问题,如下图(debug就知道为什么要初始化为1了,正确输出为1,2,初始化为0会输出2):
1 \ 2
代码如下:
- void findModeCore(TreeNode* root, TreeNode* &pre, int &cur, int &max_, vector<int> &res) {
- if (!root) {
- return;
- }
- findModeCore(root->left, pre, cur, max_,res);
- if (pre) {
- cur = (root->val == pre->val) ? (cur+1) : 1;
- }
- if (cur >= max_) {
- if (cur == max_) {
- res.push_back(root->val);
- }
- else {
- res.clear();
- res.push_back(root->val);
- max_ = cur;
- }
-
- }
- pre = root;
- findModeCore(root->right, pre, cur, max_, res);
- }
- vector<int> findMode(TreeNode* root) {
- vector<int> res;
- if (!root) {
- return res;
- }
- TreeNode* pre = nullptr;
- int cur = 1;
- int max_ = 0;
- findModeCore(root, pre, cur, max_, res);
- return res;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。