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]