C++で二分木内の合計が指定値xと等しいペアをカウントする方法

整数値と変数 x が与えられ、それらをもとに二分木を構築し、ノードの値の合計が指定値 x と等しくなるペアの個数を求めるのが課題です。

例

入力

int x = 5 の場合、値を入力して作成される二分木は次のようになります −

出力

合計が指定値 x と等しい二分木内のペアの数: 2

説明

整数値の配列から二分木を作成し、
合計が指定値 x(この場合は 5)と等しくなる
ペアが木の中に存在するかどうかを確認します。
形成されるペアは (2, 3) と (1, 4) の 2 つです。

入力

int x = 8 の場合、値を入力して作成される二分木は次のようになります −

出力

合計が指定値 x と等しい二分木内のペアの数: 3

説明

整数値の配列から二分木を作成し、
合計が指定値 x(この場合は 8)と等しくなる
ペアが木の中に存在するかどうかを確認します。
形成されるペアは (2, 6)、(4, 4)、(5, 3) の 3 つです。

以下のプログラムで使用しているアプローチは次の通りです −

• データ部分と、左右の部分木を指す left・right ポインタを持つノード構造体を作成します。

• 整数値を入力し、left・right ポインタ経由で各ノードにデータを設定することで二分木を構築します。

• 合計が x となるペアを計算するために使用する値 x を入力します。

• ペアの合計が x と一致するかどうかを判定する bool 型関数(check 関数)を作成します。

• 関数内では、まず root が NULL の場合に false を返します。

• root が ptr と同一ノードではなく、かつ root のデータ + ptr のデータが x と等しい場合は true を返します。

• root の左ポインタ、ptr、x を引数として check 関数を再帰的に呼び出し、同様に右ポインタについても呼び出します。どちらか一方でも true を返した場合は true を返します。

• 上記以外の場合は false を返します。

• 合計が x となるペアの個数を計算する total_pairs 関数を作成します。

• 関数内では、ptr が NULL の場合に 0 を返します。

• root、ptr、x を引数として check 関数を呼び出します。true が返された場合は total の値を 1 増やします。

• root、ptr の左ポインタ、x、total を引数として total_pairs 関数を再帰的に呼び出し、さらに root、ptr の右ポインタ、x、total についても呼び出します。

• 変数 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;
    return newNode;
}
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<<"合計が指定値 x と等しい二分木内のペアの数: "<< total;
    return 0;
}

出力

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

合計が指定値 x と等しい二分木内のペアの数: 2