C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++の2つの二分探索木のすべての要素

2つのバイナリ検索ツリーがあり、これらのツリーにすべての要素が存在する値のリストを返す必要があり、リスト要素は昇順になります。したがって、木が次のような場合-

C++の2つの二分探索木のすべての要素

その場合、出力は[0,1,1,2,3,4]になります。

これを解決するには、次の手順に従います-

  • ansという配列を定義し、2つのスタック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]

  1. C++の2つの二分木で最初の一致しない葉を見つけます

    2つの二分木があるとします。一致しない2本の木の最初の葉を見つける必要があります。一致しない葉がない場合は、何も表示しません。 これらが2つのツリーである場合、最初の一致しない葉は11と15です。 ここでは、スタックを使用して、両方のツリーの反復プレオーダートラバーサルを同時に使用します。ツリーごとに異なるスタックを使用します。トップノードがリーフノードになるまで、ノードをスタックにプッシュします。 2つのトップを比較し、同じ場合はさらにチェックし、そうでない場合は2つのスタックトップ要素を表示します。 例 #include <iostream> #include <

  2. C ++プログラムでの二分探索？

    二分探索は、半区間探索、対数探索、または二分探索とも呼ばれ、ソートされた配列内のターゲット値の位置を見つける検索アルゴリズムです。二分探索は、ターゲット値を配列の中央の要素と比較します。それらが等しくない場合、ターゲットが存在できない半分が削除され、残りの半分で検索が続行され、再び中央の要素がターゲット値と比較され、ターゲット値が見つかるまでこれが繰り返されます。残りの半分が空の状態で検索が終了した場合、ターゲットは配列に含まれていません。アイデアは単純ですが、バイナリ検索を正しく実装するには、特に配列の値が範囲内の整数のすべてではない場合、終了条件と中間点の計算に関する微妙な点に注意する必要