C++ में दो बाइनरी ट्री मर्ज करें

मान लीजिए कि हमारे पास दो बाइनरी पेड़ हैं और विचार करें कि जब हम उनमें से एक को दूसरे को कवर करने के लिए रखते हैं, तो दो पेड़ों के कुछ नोड्स ओवरलैप हो जाते हैं जबकि अन्य ओवरलैपिंग होते हैं। हमें उन्हें एक नए बाइनरी ट्री में मिलाना होगा। मर्ज नियम इस तरह है कि यदि दो नोड्स ओवरलैपिंग कर रहे हैं, तो नोड को मर्ज किए गए नोड के नए मान के रूप में जोड़ दें। अन्यथा, गैर-रिक्त नोड का उपयोग नए ट्री के नोड के रूप में किया जाएगा।

तो अगर पेड़ हैं -

तब आउटपुट होगा -

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

• विधि मर्जट्रीज़ () है। यह दो ट्री नोड्स n1 और n2 लेता है। यह इस प्रकार है

• यदि n1 खाली है, और n2 गैर-रिक्त है, तो n2 लौटाएं, अन्यथा जब n2 खाली हो, और n1 खाली न हो, तो n1 लौटाएं, और जब दोनों शून्य हों, तो अशक्त लौटें

• n1 का मान :=n1 का मान + n2 का मान

• n1 के बाएँ :=मर्जट्रीज़ (n1 के बाएँ, n2 के बाएँ)

• n1 का अधिकार:=मर्ज ट्री (n1 का दायां, n2 का दायां)

• वापसी n1

उदाहरण (C++)

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

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = 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){
         temp->left = new TreeNode(val);
         return;
      }
      else{
         q.push(temp->left);
      }
      if(!temp->right){
         temp->right = new TreeNode(val);
         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;
}
void tree_level_trav(TreeNode*root){
   if (root == NULL) return;
   cout << "[";
   queue<TreeNode *> q;
   TreeNode *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
      }
      else {
         if(curr->left)
            q.push(curr->left);
         if(curr->right)
            q.push(curr->right);
         if(curr->val == 0){
            cout << "null" << ", ";
         }
         else{
            cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
public:
   TreeNode* mergeTrees(TreeNode* n1, TreeNode* n2) {
      if(!n1 && n2){
         return n2;
      }
      else if(!n2 && n1)return n1;
      else if(!n1 && !n2)return NULL;
      n1->val+=n2->val;
      n1->left = mergeTrees(n1->left,n2->left);
      n1->right = mergeTrees(n1->right,n2->right);
      return n1;
   }
};
main(){
   Solution ob;
   vector<int> v1 = {1,3,2,5};
   vector<int> v2 = {2,1,3,NULL,4,NULL,7};
   TreeNode *root1 = make_tree(v1);
   TreeNode *root2 = make_tree(v2);
   root1 = ob.mergeTrees(root1, root2);
   tree_level_trav(root1);
}

इनपुट

[1,3,2,5]
[2,1,3,null,4,null,7]

आउटपुट

[3, 4, 5, 5, 4, null, 7, ]