Tất cả các phần tử trong hai cây tìm kiếm nhị phân trong C ++

Giả sử chúng ta có hai cây tìm kiếm nhị phân, chúng ta phải trả về một danh sách các giá trị có tất cả các phần tử có trong các cây này và các phần tử trong danh sách sẽ theo thứ tự tăng dần. Vì vậy, nếu cây cối giống như -

Khi đó đầu ra sẽ là [0,1,1,2,3,4].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng được gọi là ans, xác định hai ngăn xếp st1 và st2
• curr1:=root1 và curr2:=root2
• chèn nút root1 và tất cả các nút bên trái vào st1, chèn nút root2 và tất cả các nút bên trái vào st2
• while st1 không trống hoặc st2 không trống
  • nếu st1 không trống và (st2 trống hoặc giá trị nút trên cùng của st1 <=giá trị nút trên cùng của st2)
    • temp:=top of st1, xóa nút khỏi st1
    • chèn giá trị tạm thời vào ans
    • chèn nút bên phải của tạm thời và tất cả các nút bên trái của nó vào st1
  • Nếu không -
    • temp:=top of st2, xóa nút khỏi st2
    • chèn giá trị tạm thời vào ans
    • chèn nút bên phải của tạm thời và tất cả các nút bên trái của nó vào st2
• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

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