องค์ประกอบทั้งหมดในทรีไบนารีค้นหาสองทรีใน 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
• คืนสินค้า

ตัวอย่าง(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]