C++ में दो बाइनरी सर्च ट्रीज़ के सभी एलिमेंट्स

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

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

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

• ans नामक एक ऐरे परिभाषित करें, दो स्टैक्स st1 और st2 परिभाषित करें
• curr1 := root1 और curr2 := root2
• नोड root1 और उसके सभी लेफ्ट नोड्स को st1 में डालें, नोड root2 और उसके सभी लेफ्ट नोड्स को st2 में डालें
• जब तक st1 खाली नहीं है या st2 खाली नहीं है
  • यदि st1 खाली नहीं है, और (st2 खाली है या st1 के टॉप नोड का मान <= st2 के टॉप नोड का मान)
    • temp := st1 का टॉप, st1 से नोड डिलीट करें
    • temp के मान को ans में डालें
    • temp के राइट नोड और उसके सभी लेफ्ट नोड्स को st1 में डालें
  • अन्यथा -
    • temp := st2 का टॉप, st2 से नोड डिलीट करें
    • temp के मान को ans में डालें
    • temp के राइट नोड और उसके सभी लेफ्ट नोड्स को st2 में डालें
• ans लौटाएं

उदाहरण (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]