C++ में सबसे अधिक बार आने वाला सबट्री योग

मान लीजिए कि हमारे पास एक पेड़ की जड़ है, हमें सबसे लगातार उप-योग का पता लगाना है। एक नोड का सबट्री योग वास्तव में उस नोड (नोड सहित) पर रूट किए गए सबट्री द्वारा गठित सभी नोड मानों का योग है। सबसे लगातार सबट्री योग वास्तव में है यदि कोई टाई है, तो सभी मानों को किसी भी क्रम में उच्चतम आवृत्ति के साथ वापस कर दें। तो अगर पेड़ [5,2,-5] जैसा है, तो वह वापस आ जाएगा [2]। ऐसा इसलिए है क्योंकि 2 दो बार होता है, हालांकि -5 केवल एक बार होता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• दो मानचित्र m और freq को परिभाषित करें, m पूर्णांक कुंजी और संबंधित सूचियों का एक सेट है, और freq प्रत्येक संख्या की आवृत्ति को संग्रहीत करेगा।

• हल () नामक एक विधि को परिभाषित करें, यह ट्री नोड लेगा। यह इस प्रकार कार्य करेगा -

• यदि नोड शून्य है, तो वापस 0

• लेफ्टसम:=सॉल्व (नोड के बाएं), राइटसम:=सॉल्व (नोड का राइट)

• currSum :=नोड मान + लेफ्टसम + राइटसम

• यदि आवृत्ति गणना currSum के समान नहीं है, तो

  • m[1] पर मौजूद सूची में currSum डालें

  • फ़्रीक सेट करें [करसम] :=1

• अन्यथा

  • freq[currSum] को 1 से बढ़ाएं

  • m[freq[currSum]]

    . पर मौजूद सूची में currSum डालें

• वापसी करसम

• मुख्य विधि इस प्रकार होगी -

• यदि रूट शून्य है, तो खाली सेट लौटाएं

• हल (रूट)

• मानचित्र की अंतिम सूची m

  . लौटाएं

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      } else {
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   map <int, vector <int> > m;
   map <int, int > freq;
   int solve(TreeNode* node){
      if(!node)return 0;
      int leftSum = solve(node->left);
      int rightSum = solve(node->right);
      int currSum = node->val + leftSum + rightSum;
      //cout << currSum << endl;
      if(!freq.count(currSum)){
         m[1].push_back(currSum);
         freq[currSum] = 1;
         //cout << "Adding " << currSum << " 1" << endl;
      } else {
         freq[currSum]++;
         m[freq[currSum]].push_back(currSum);
      }
      return currSum;
   }
   vector<int> findFrequentTreeSum(TreeNode* root) {
      m.clear();
      freq.clear();
      if(!root)return {};
      solve(root);
      return m.rbegin()->second;
   }
};
main(){
   vector<int> v = {5,2,-5};
   TreeNode *tree = make_tree(v);
   Solution ob;
   print_vector(ob.findFrequentTreeSum(tree));
}

इनपुट

[5,2,-5]

आउटपुट

[2, ]