版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010529144/article/details/72717289
1.题目
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].
给一棵二叉搜索树,有重复元素。找出其中重复次数最多的元素。如果有多个重复次数一样的元素,则放在一个列表中作为返回结果。
2.分析
这题考察的是BST的中序遍历,中序遍历的元素是有序的,在遍历的过程中统计元素出现的次数即可。
3.代码
中序遍历–迭代
class Solution {
public :
vector <int > findMode(TreeNode* root) {
vector <int > mode;
if (root == NULL)
return mode;
int max_c = -1 ;
int last_v = INT_MIN;
int count = 1 ;
stack <TreeNode*> nodes;
while (!nodes.empty() || root) {
if (root) {
nodes.push(root);
root = root->left;
}
else {
root = nodes.top();
nodes.pop();
if (last_v != INT_MIN) {
if (root->val == last_v)
++count;
else
count = 1 ;
}
if (count > max_c)
{
max_c = count;
mode.erase(mode.begin(), mode.end());
mode.push_back(root->val);
}
else if (count == max_c)
mode.push_back(root->val);
last_v = root->val;
root = root->right;
}
}
return mode;
}
};
中序遍历–递归
class Solution {
public :
void inOrder(TreeNode* root, vector <int > &mode,int & val,int & count,int & maxc) {
if (root == NULL)
return ;
inOrder(root->left,mode,val,count,maxc);
if (val != INT_MIN) {
if (val == root->val)
++count;
else
count = 1 ;
}
if (count > maxc) {
maxc = count;
mode.erase(mode.begin(), mode.end());
mode.push_back(root->val);
}
else if (count == maxc)
mode.push_back(root->val);
val = root->val;
inOrder(root->right, mode, val, count, maxc);
}
vector <int > findMode(TreeNode* root) {
vector <int > mode;
if (root == NULL)
return mode;
int maxc = -1 ;
int count = 1 ;
int val = INT_MIN;
inOrder(root, mode, val, count, maxc);
return mode;
}
};