Частота узла/значения в двоичном дереве поиска

Question

Учитывая двоичное дерево поиска, где могут быть дубликаты, но всякая другая логика 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).

Answer 1

Я вижу, что вы сами исправили некоторые проблемы. Во всяком случае, я решил полностью решить это, изменив несколько вещей, чтобы упростить все. Он использует 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 &current, int &currentCount) 
{ 
    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; 
} 

Он использует тот факт, что, так как это БСТ, пересекая его в [влево -> ток -> правый] порядок будет приводить к сортируется элементы, вот и все.