Task
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:
- The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
-Both the left and right subtrees must also be binary search trees.
Examples
For example:
Given BST [1,null,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).
Solution
- 查找BST中出现次数最多的元素，使用中序遍历，问题转化为：遍历一个升序数组，只需在每看到新值时对其计数。
- 可以直接用哈希表存储计数值，但这用不到升序排列的特性，可能会较慢。
- 在中序遍历时一边统计计数一边维护一个vector作为输出结果ans_：
- 维护3个变量：看到的上一个数字before_，当前计数值cnt_，到目前的最大计数max_cnt_
- 若当前值是新值，更新before_并重新开始计数cnt_=1
- 若当前值不是新值，则计数增加++cnt_
- 若计数增加到和之前的最大计数max_cnt_一样大，则将当前值存入ans_
- 若计数增加到比max_cnt_还大，则更新max_cnt_并将ans_清空并存入新值
- 时间复杂度：遍历每个节点，每个节点的时间是O(1)，故总时间复杂度是O(n)
- 空间复杂度：仅使用3个计数变量，空间复杂度是O(1)
- 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
// Runtime: 24 ms, faster than 84.66% of C++ online submissions for Find Mode in Binary Search Tree.
// Memory Usage: 24.2 MB, less than 53.39% of C++ online submissions for Find Mode in Binary Search Tree.
/**
* Definition for a binary tree node.
* 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 {
public:
vector<int> findMode(TreeNode* root) {
inorder(root);
return ans_;
}
private:
//维护输出vector所需的临时变量和计数变量
int before_=0,cnt_=0,max_cnt_=0;
vector<int> ans_;
//中序遍历
void inorder(TreeNode *root){
if(!root) return;
inorder(root->left);
visit(root->val);
inorder(root->right);
}
//每访问一个节点的操作
void visit(int val){
//cnt_>0是为处理初始情形，val==before_是对已经有重复的值，则计数增加
if(cnt_>0 && val==before_)
++cnt_;
//对于新值，更新before_并重置计数
else{
before_=val;
cnt_=1;
}
//计数达到最多时将val放入结果中
if(cnt_==max_cnt_)
ans_.push_back(val);
//计数比之前的最大值还大，则更新计数最大值并清空之前的结果
if(cnt_>max_cnt_){
max_cnt_=cnt_;
ans_.clear();
ans_.push_back(val);
}
}
};
|
- 也可用另一种实现：中序遍历两次，第一次找最高频率是多少（增加一个计数值mode_cnt_），第二次直接查找频率为该值的元素。
- 这样虽然要遍历两次，但是减少了不断操作vector的开销
- 时间复杂度和空间复杂度均同上一种实现
- 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
// Runtime: 20 ms, faster than 94.84% of C++ online submissions for Find Mode in Binary Search Tree.
// Memory Usage: 24 MB, less than 67.55% of C++ online submissions for Find Mode in Binary Search Tree.
/**
* Definition for a binary tree node.
* 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 {
public:
vector<int> findMode(TreeNode* root) {
//第一次中序遍历，查找最高频率
inorder(root);
//清空计数值，并给最高频率赋值
cnt_=0;
mode_cnt_=max_cnt_;
//第二次中序遍历，根据得到的最高频率来取元素
inorder(root);
return ans_;
}
private:
int before_=0,cnt_=0,max_cnt_=0,mode_cnt_=0;
vector<int> ans_;
void inorder(TreeNode *root){
if(!root) return;
inorder(root->left);
visit(root->val);
inorder(root->right);
}
void visit(int val){
if(cnt_>0 && val==before_)
++cnt_;
else{
before_=val;
cnt_=1;
}
//第一次中序遍历时起作用，用于维护最高频率值
if(cnt_>max_cnt_)
max_cnt_=cnt_;
//第二次中序遍历时起作用，根据最高频率取元素
if(cnt_==mode_cnt_)
ans_.push_back(val);
}
};
|