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.
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)
适应于任何树的方法，直接遍历法。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
unordered_map<int,int>all;
void traversal(TreeNode* root)
{
if(!root) return;
all[root->val]++;
traversal(root->left);
traversal(root->right);
}
public:
vector<int> findMode(TreeNode* root) {
vector<int>res;
if(!root) return res;
traversal(root);
int count=0;
for(auto& a: all)
{
count = max(count, a.second);
}
for(auto& a:all)
if(a.second == count) res.push_back(a.first);
return res;
}
};
执行用时 :52 ms, 在所有 C++ 提交中击败了22.86%的用户 内存消耗 :27.1 MB, 在所有 C++ 提交中击败了12.78%的用户
考虑到是BST，可以充分利用其已经排好序的先验知识。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
void traversal(TreeNode* cur, TreeNode*& pre, int& cnt, int& max_cnt,vector<int>& res)
{
if(!cur) return;
traversal(cur->left,pre,cnt,max_cnt,res);
if(pre)
cnt = cur->val == pre->val ? cnt+1: 1 ;
pre=cur;
if(cnt>max_cnt)
{
max_cnt=cnt;
res.clear();
res.push_back(cur->val);
}
else if(cnt == max_cnt )
res.push_back(cur->val);
traversal(cur->right,pre,cnt,max_cnt,res);
}
public:
vector<int> findMode(TreeNode* root) {
vector<int>res;
if(!root) return res;
int count=1;
int max_cnt=0;
TreeNode* pre=nullptr;
traversal(root,pre,count,max_cnt, res);
return res;
}
};
执行用时 :32 ms, 在所有 C++ 提交中击败了72.22%的用户 内存消耗 :23MB, 在所有 C++ 提交中击败了95.89%的用户
Last modified 1yr ago