Powered By GitBook
501.Find Mode in Binary Tree

501.Find Mode in Binary Search Tree

难度:Easy
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.
1
For example:
2
Given BST [1,null,2,2],
3
4
1
5
\
6
2
7
/
8
2
9
10
11
return [2].
12
13
Note: If a tree has more than one mode, you can return them in any order.
Copied!
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count)
适应于任何树的方法,直接遍历法。
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
unordered_map<int,int>all;
12
void traversal(TreeNode* root)
13
{
14
if(!root) return;
15
all[root->val]++;
16
traversal(root->left);
17
traversal(root->right);
18
}
19
public:
20
vector<int> findMode(TreeNode* root) {
21
vector<int>res;
22
if(!root) return res;
23
traversal(root);
24
int count=0;
25
for(auto& a: all)
26
{
27
count = max(count, a.second);
28
}
29
for(auto& a:all)
30
if(a.second == count) res.push_back(a.first);
31
return res;
32
}
33
};
Copied!
执行用时 :52 ms, 在所有 C++ 提交中击败了22.86%的用户 内存消耗 :27.1 MB, 在所有 C++ 提交中击败了12.78%的用户
考虑到是BST,可以充分利用其已经排好序的先验知识。
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
void traversal(TreeNode* cur, TreeNode*& pre, int& cnt, int& max_cnt,vector<int>& res)
12
{
13
if(!cur) return;
14
traversal(cur->left,pre,cnt,max_cnt,res);
15
if(pre)
16
cnt = cur->val == pre->val ? cnt+1: 1 ;
17
pre=cur;
18
if(cnt>max_cnt)
19
{
20
max_cnt=cnt;
21
res.clear();
22
res.push_back(cur->val);
23
}
24
else if(cnt == max_cnt )
25
res.push_back(cur->val);
26
traversal(cur->right,pre,cnt,max_cnt,res);
27
28
}
29
public:
30
vector<int> findMode(TreeNode* root) {
31
vector<int>res;
32
if(!root) return res;
33
int count=1;
34
int max_cnt=0;
35
TreeNode* pre=nullptr;
36
traversal(root,pre,count,max_cnt, res);
37
return res;
38
}
39
};
Copied!
执行用时 :32 ms, 在所有 C++ 提交中击败了72.22%的用户 内存消耗 :23MB, 在所有 C++ 提交中击败了95.89%的用户
Last modified 2yr ago
Copy link