合計がC++の指定された値xに等しい2つのBSTからペアをカウントします

入力として2つの二分探索木と変数xが与えられます。目標は、ノードの値の合計がxに等しくなるように、各ツリーからノードのペアを見つけることです。 BST_1からノード1を取得し、BST_2からノード2を取得して、両方のデータ部分を追加します。 sum=xの場合。インクリメントカウント。

例を挙げて理解しましょう。

入力

出力 −合計が特定の値xに等しい2つのBSTからのペアの数は− 1

説明 −ペアは（8,6）

入力

出力 −合計が特定の値xに等しい2つのBSTからのペアの数は− 2

説明 −ペアは（5,15）と（4,16）

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、反復順序法を使用してBSTをトラバースします。反復順序法を使用して最小ノードから最大ノードにBST1をトラバースし、反復順序法の逆からBST2をトラバースします。両方のBSTの現在のノードの合計を取ります。合計がxインクリメントカウントの場合。 sum> xの場合、BST2の現在のノードの順序の前の先行に移動します。sum

• 整数データ部分と子ノードへの左右のポインタを持つ2つのツリーBST_1とBST_2を取ります。

• 関数insert_node（int data）は、データを含むツリーに新しいノードを挿入し、そのノードへのポインターを返します。

• inser_node（）を使用して両方のBSTを作成し、BST_sum_x（Tree * BST_1、Tree * BST_2、int x）に渡します。

• 関数BST_sum_x（Tree * BST_1、Tree * BST_2、int x）は、両方のツリーのルートノードを取得し、データ部分の合計をxとして持つノードのペアの数を返します。

• 合計xのペアの数の初期カウントを0とします。

• 反復的な順序トラバーサルの場合、2つの変数Tree * stack_top_1、* stack_top_2;

  を取ります。

• 2つのスタックを作成しますstackstack_1、stack_2;

• 次に、外側のwhileループを開始します。

• whileループを使用してBST_1の左端（最小）のノードに移動し、すべてのノードをstack_1にプッシュします

• whileループを使用してBST_2の右端（最大）のノードに移動し、すべてのノードをstack_2にプッシュします

• スタックのいずれかが空の場合は、外側のwhileループを解除します。

• 両方のスタックの最上位ノードを取得し、それらのデータパーツを追加して、一時的に保存します。

• temp（sum）==xの場合、カウントをインクリメントします。ポップ操作を使用して、stack_1とstack_2の両方から最上位の要素を削除します。

• BST_1 =stack_1->rightおよびBST_2=stack_2-> left（BST_1の次の後続およびBST_2の先行）を設定します

• temp

• temp> xの場合、stack_2からtopのみを削除し、BST_1の次の先行タスクに移動します。

• 外側のwhileの終わりに、countには、合計xを持つ両方のBSTのノードを持つペアの数があります。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
struct Tree{
   int data;
   Tree* left, *right;
};
Tree* insert_node(int data){
   Tree* newNode = (Tree*)malloc(sizeof(Tree));
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;
}
int BST_sum_x(Tree* BST_1, Tree* BST_2, int x){
   int count = 0;
   Tree* stack_top_1, *stack_top_2;
   stack<Tree*> stack_1, stack_2;
   if (BST_1 == NULL || BST_2 == NULL){
      return 0;
   }
   while (1){
      while (BST_1 != NULL){
         stack_1.push(BST_1);
         BST_1 = BST_1->left;
      }
      while (BST_2 != NULL){
         stack_2.push(BST_2);
         BST_2 = BST_2->right;
      }
      if (stack_1.empty() || stack_2.empty()){
         break;
      }
      stack_top_1 = stack_1.top();
      stack_top_2 = stack_2.top();
      int temp = stack_top_1->data + stack_top_2->data;
      if (temp == x){
         count++;
         stack_1.pop();
         stack_2.pop();
         BST_1 = stack_top_1->right;
         BST_2 = stack_top_2->left;
      }
      else if (temp < x){
         stack_1.pop();
         BST_1 = stack_top_1->right;
      }
      else{
         stack_2.pop();
         BST_2 = stack_top_2->left;
      }
   }
   return count;
}
int main(){
   //BST 1
   Tree* BST_1 = insert_node(15);
   BST_1->left = insert_node(10);
   BST_1->right = insert_node(8);
   BST_1->left->left = insert_node(12);
   BST_1->left->right = insert_node(24);
   BST_1->right->left = insert_node(16);
   //BST 2
   Tree* BST_2 = insert_node(20);
   BST_2->left = insert_node(16);
   BST_2->right = insert_node(4);
   BST_2->left->left = insert_node(18);
   BST_2->left->right = insert_node(28);
   BST_2->right->left = insert_node(22);
   int x = 28;
   cout<<"Count of pairs from two BSTs whose sum is equal to a given value x ar: "<<BST_sum_x(BST_1, BST_2, x);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of pairs from two BSTs whose sum is equal to a given value x ar: 1