Учитывая бинарное дерево поиска, где могут содержаться дубликаты, но вся остальная логика BST не повреждена, определяют наиболее часто встречающийся элемент.
class TreeNode
{
public:
TreeNode* right = NULL;
TreeNode* left = NULL;
int val;
TreeNode(int value)
{
val = value;
}
};
// To keep track of the frequency of the value/node
struct holder
{
public:
TreeNode* most = NULL;
int count = 0;
};
int frequencyOfNode(TreeNode* root, struct holder* ptr)
{
if (root == NULL)
{
return 0;
}
int left = frequencyOfNode(root->left, ptr);
int right = frequencyOfNode(root->right, ptr);
// need to check of left and right are nor null
if (left != 0 && root->val == root->left->val)
{
return 1 + left;
}
else if (right != 0 && root->val == root->right->val)
{
return 1 + right;
}
else
{
// left has a higher frequency
if (left >= right)
{
// left is bigger;
if (left > ptr->count)
{
ptr->most = root->left;
ptr->count = left;
}
}
else
{
// right has a higher frequency
if (right > ptr->count)
{
ptr->most = root->right;
ptr->count = right;
}
}
return 1;
}
}
Я делаю обход по порядку в двоичном дереве поиска.
моя логика работает, когда узлы появляются в последовательном порядке, но если узел не в последовательном порядке; частота узла сбрасывается.
мое время O (n) и пространство O (1).
проблема в том, что узлы не связаны подряд.
мой образец дерева:
int main()
{
TreeNode *root = new TreeNode(6);
root->right = new TreeNode(8);
root->right->left = new TreeNode(7);
root->right->right = new TreeNode(8);
root->right->right->right = new TreeNode(8);
root->right->right->right->right = new TreeNode(9);
root->right->right->right->right->left = new TreeNode(8);
root->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->left->right->right = new TreeNode(5);
root->left->right->right->right = new TreeNode(5);
root->left->left = new TreeNode(1);
root->left->left->right = new TreeNode(1);
root->left->left->right->right = new TreeNode(1);
root->left->left->right->right = new TreeNode(2);
root->left->left->left = new TreeNode(0);
struct holder freq;
int ran = frequencyOfNode(root, &freq);
std::cout << "random" << ran << std::endl;
std::cout << "The Node: " << freq.most->val << " frequency " << freq.count
<< std::endl;
return 0;
}
Я действительно запутался в том, как учитывать, когда узлы не являются последовательными (т. Е. 8-> 8-> 8-> 9-> 8).
Я вижу, вы сами исправили некоторые проблемы. Во всяком случае, я решил решить это полностью, изменив несколько вещей, чтобы упростить все. Он использует O (N) время и пространство O (1):
#include <iostream>
#include <limits>
class TreeNode
{
public:
TreeNode* right;
TreeNode* left;
int val;
TreeNode(int value)
{
val = value;
right = left = NULL;
}
};
// To keep track of the frequency of the value/node
struct Holder
{
public:
int value;
int count;
Holder(int v=std::numeric_limits<int>::min(), int c=-1): value(v), count(c) {}
};void dfs(TreeNode* root, int &mostFrequent, int &mostFrequentCount, int ¤t, int ¤tCount)
{
if(root->left) dfs(root->left, mostFrequent, mostFrequentCount, current, currentCount); //first go to smaller
int val = root->val;
if(val == current) currentCount++;
else { current=val; currentCount=1; }
if(currentCount > mostFrequentCount)
{
mostFrequent=current;
mostFrequentCount=currentCount;
}
if(root->right) dfs(root->right, mostFrequent, mostFrequentCount, current, currentCount); //finally go to larger
}
Holder getMostFrequent(TreeNode *root)
{
int mostFrequent=-1,mostFrequentCount=-1, current=std::numeric_limits<int>::min(), currentCount=-1;
if(root) dfs(root, mostFrequent, mostFrequentCount, current, currentCount);
return Holder(mostFrequent, mostFrequentCount);
}int main()
{
TreeNode *root = new TreeNode(6);
root->right = new TreeNode(8);
root->right->left = new TreeNode(7);
root->right->right = new TreeNode(8);
root->right->right->right = new TreeNode(8);
root->right->right->right->right = new TreeNode(9);
root->right->right->right->right->left = new TreeNode(8);
root->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->left->right->right = new TreeNode(5);
root->left->right->right->right = new TreeNode(5);
root->left->left = new TreeNode(1);
root->left->left->right = new TreeNode(1);
root->left->left->right->right = new TreeNode(1);
root->left->left->right->right = new TreeNode(2);
root->left->left->left = new TreeNode(0);
Holder h = getMostFrequent(root);
std::cout << "most frequently encountered element: " << h.value << ", " << h.count << " times\n";return 0;
}
Он использует тот факт, что, поскольку это BST, его обход в порядке [left -> current -> right] приведет к сортировке элементов, вот и все.
Других решений пока нет …