C++ में दो बाइनरी सर्च ट्री में सभी तत्व

मान लीजिए कि हमारे पास दो बाइनरी सर्च ट्री हैं, हमें मानों की एक सूची वापस करनी होगी, जिसमें इन पेड़ों में सभी तत्व मौजूद हैं, और सूची तत्व आरोही क्रम में होंगे। तो अगर पेड़ जैसे हैं -

तब आउटपुट [0,1,1,2,3,4] होगा।

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

• एक सरणी को परिभाषित करें जिसे ans कहा जाता है, दो स्टैक st1 और st2 परिभाषित करें
• curr1 :=root1 और curr2 :=root2
• नोड रूट1 और सभी बाएं नोड्स को st1 में डालें, नोड रूट2 और सभी बाएं नोड्स को st2 में डालें
• जबकि st1 खाली नहीं है या st2 खाली नहीं है
  • यदि st1 खाली नहीं है, और (st2 खाली है या st1 का शीर्ष नोड मान <=st2 का शीर्ष नोड मान)
    • अस्थायी:=st1 के ऊपर, st1 से नोड हटाएं
    • अस्थायी का मान ans में डालें
    • अस्थायी के दाएं नोड और उसके सभी बाएं नोड्स को st1 में डालें
  • अन्यथा −
    • अस्थायी:=st2 के ऊपर, st2 से नोड हटाएं
    • अस्थायी का मान ans में डालें
    • अस्थायी के दाएं नोड और उसके सभी बाएं नोड्स को st2 में डालें
• वापसी उत्तर

उदाहरण(C++)

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

#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:
   void pushLeft(stack <TreeNode*>& st, TreeNode* root){
      TreeNode* curr = root;
      while(curr){
         st.push(curr);
         curr = curr->left;
      }
   }
   vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
      vector <int> ans;
      stack <TreeNode*> st1, st2;
      TreeNode* curr1 = root1;
      TreeNode* curr2 = root2;
      pushLeft(st1, curr1);
      pushLeft(st2, curr2);
      while(!st1.empty() || !st2.empty()){
         TreeNode* temp;
         if(!st1.empty() && (st2.empty() || st1.top()->val <= st2.top()->val)){
            temp = st1.top();
            st1.pop();
            ans.push_back(temp->val);
            pushLeft(st1, temp->right);
         }
         else{
            temp = st2.top();
            st2.pop();
            ans.push_back(temp->val);
            pushLeft(st2, temp->right);
         }
      }
      return ans;
   }
};
main(){
   vector<int> v = {2,1,4};
   TreeNode *root1 = make_tree(v);
   v = {1,0,3};
   TreeNode *root2 = make_tree(v);
   Solution ob;
   print_vector(ob.getAllElements(root1, root2));
}

इनपुट

[2,1,4]
[1,0,3]

आउटपुट

[0,1,1,2,3,4]