合計がC++の指定された値xに等しい二分木のペアをカウントします

整数値と変数xが与えられ、タスクは二分木を構築し、与えられた値xに等しい合計を持つペアを見つけることです。

例

入力

int x =5、値を入力した後に作成されるツリーを以下に示します-

出力

Count of pairs in a binary tree whose sum is equal to a given value x are: 2

説明

we are given with an array of integer values that is used to form a binary
tree and we will check whether there is a pair present in a binary tree whose sum
equals to the given value x which is 5. So, the pairs formed are (2, 3) and (1, 4).

入力

int x =8、値を入力した後に作成されるツリーを以下に示します-

出力

Count of pairs in a binary tree whose sum is equal to a given value x are: 3

説明

we are given with an array of integer values that is used to form a binary
tree and we will check whether there is a pair present in a binary tree whose sum
equals to the given value x which is 8. So, the pairs formed are (2, 6), (4, 4) and (5, 3).

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

• データ部分と、左右のサブツリーを指す左右のポインタを含むノードの構造を作成します。

• 整数値を入力し、それらを使用して、左右のポインターを介してノードにデータを入力することにより、バイナリツリーを作成します。

• xの値を入力します。これは、xの時点で合計値を持つペアを計算するために使用されます。

• ペアの合計がxであるかどうかを確認するブール関数を作成します。

• 関数内で、rootがNULLかどうかを確認してから、Falseを返します

• ルートがptrに等しくなく、ルートのデータ+ptrのデータがxに等しいかどうかを確認してからTrueを返します。

• root、ptr、および値xの左ポインターと、x、ptr、およびxの右ポインターを渡すことにより、check関数を再帰的に呼び出します。次に、いずれかの条件がtrueを返しているかどうかを確認してから、trueを返します。

• それ以外の場合は、falseを返します。

• 関数total_pairsを作成して、合計をxとしてペアの数を計算します

• 関数内で、ptrがNULLかどうかを確認してから、0を返します。

• root、ptr、xを引数として渡して、関数チェックを呼び出します。関数がtrueを返す場合は、ペアの合計値を1ずつインクリメントします

• ルート、ptr、x、およびtotalの左ポインターを渡し、ルート、ptr、x、およびtotalの右ポインターも渡すことにより、関数total_pairsを再帰的に呼び出します。

• 結果を変数totalに格納された整数値として出力します。

例

#include <bits/stdc++.h>
using namespace std;
struct tree_node {
   int data;
   tree_node *left, *right;
};
tree_node* create_node(int data){
   tree_node* newNode = (tree_node*)malloc(sizeof(tree_node));
   newNode−>data = data;
   newNode−>left = newNode−>right = NULL;
}
bool check(tree_node* root, tree_node* ptr, int x){
   if(root==NULL){
      return false;
   }
   if (root != ptr && ((root−>data + ptr−>data) == x)){
      return true;
   }
   if (check(root−>left, ptr, x) || check(root−>right, ptr, x)){
      return true;
   }
   return false;
}
void total_pairs(tree_node* root, tree_node* ptr, int x, int& total){
   if(ptr == NULL){
      return;
   }
   if(check(root, ptr, x) == true){
      total++;
   }
   total_pairs(root, ptr−>left, x, total);
   total_pairs(root, ptr−>right, x, total);
}
int main(){
   int x = 5;
   int total = 0;
   tree_node* root = create_node(5);
   root−>left = create_node(2);
   root−>right = create_node(3);
   root−>left−>left = create_node(1);
   root−>left−>right = create_node(4);
   root−>right−>left = create_node(6);
   total_pairs(root, root, x, total);
   total = total / 2;
   cout<<"Count of pairs in a binary tree whose sum is equal to a given value x are: "<< total;
   return 0;
}

出力

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

Count of pairs in a binary tree whose sum is equal to a given value x are: 2