Häufigkeit von Knoten/Wert in einem binären Suchbaum

Question

Gegeben ein binärer Suchbaum, in dem Duplikate enthalten sein können, aber alle anderen Logik des BST intakt ist, bestimmen Sie das am häufigsten vorkommende Element.

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; 
    } 
} 

Ich mache eine Nachbestellung Traversal des binären Suchbaums. meine Logik funktioniert, wenn die Knoten in fortlaufender Reihenfolge angezeigt werden, aber wenn der Knoten nicht in fortlaufender Reihenfolge ist; Die Frequenz des Knotens wird zurückgesetzt.

meine Zeit ist O (n) und der Raum ist O (1).

das Problem ist, wenn die Knoten nicht in Folge verbunden sind.

meine Probe Baum:

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; 
} 

Ich bin wirklich verwirrt, wie zu berücksichtigen, wenn die Knoten nicht aufeinander folgend sind (das heißt 8-> 8-> 8-> 9-> 8).

Answer 1

Ich sehe, Sie haben einige Probleme selbst behoben. Wie auch immer, ich habe beschlossen, das komplett zu lösen und auch ein paar Dinge zu ändern, um alles zu vereinfachen. Es nutzt O (N) Zeit und O (1) Raum:

#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; 
} 

Es nutzt die Tatsache, dass da dies ein BST, es in dem durchquert [links -> Strom -> rechts], um in sortierte führen würde Elemente, das ist alles.