C++で任意の二分木をChildren Sum Property（子の和の性質）を満たす木に変換する方法

本記事では、C++を用いて任意の二分木を「Children Sum Property（子の和の性質）」を満たす二分木へ変換するプログラムについて解説します。

Children Sum Propertyとは、すべての内部ノードにおいて「親ノードの値 ＝ 左の子の値 ＋ 右の子の値」が成り立つ性質のことです。子が1つしかないノードの場合は、その唯一の子の値と親の値が一致していればよいことになります。

問題の概要と制約

入力として二分木が与えられ、これをChildren Sum Propertyを満たす形に変換するのが目的です。ただし、以下の制約を守る必要があります。

• ノードの値は増加させることのみ可能であり、減少させることはできません。
• 木の構造（ノード同士のつながり）は変更してはなりません。

変換アルゴリズムの考え方

変換は木をボトムアップ（葉から根へ）再帰的に処理することで実現できます。手順は次のとおりです。

1. 現在のノードがNULL、または葉ノードであれば何もしません（葉ノードは自動的に性質を満たすため）。
2. まず左部分木と右部分木をそれぞれ再帰的に変換します。
3. 左右の子の値の合計と現在のノードの値との差分（diff）を計算します。
4. diff > 0 の場合（子の合計が親より大きい）：親ノードの値にdiffを加算すれば、値の増加だけで性質を満たせます。
5. diff < 0 の場合（子の合計が親より小さい）：親の値は減らせないため、代わりにいずれかの子ノードから順に、差分の絶対値分だけ値を増やしていきます。

C++による実装例

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

// 二分木のノード構造体
class node {
public:
    int data;
    node* left;
    node* right;
    // 新しいノードの生成
    node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

// 子ノード側の値を増加させる関数（前方宣言）
void increment(node* node, int diff);

// 木をChildren Sum Propertyを満たす形へ変換するメイン関数
void convert_Btree(node* node) {
    int left_data = 0, right_data = 0, diff;
    // ルートがNULL、または葉ノードの場合はそのまま返す
    if (node == NULL || (node->left == NULL && node->right == NULL))
        return;
    else {
        // 左右の部分木を再帰的に変換
        convert_Btree(node->left);
        convert_Btree(node->right);
        if (node->left != NULL)
            left_data = node->left->data;
        if (node->right != NULL)
            right_data = node->right->data;
        // 子の値の合計との差分を求める
        diff = left_data + right_data - node->data;
        // 子の合計が親より大きい場合は親の値を増加させる
        if (diff > 0)
            node->data = node->data + diff;
        // 子の合計が親より小さい場合は子側の値を増加させる
        if (diff < 0)
            increment(node, -diff);
    }
}

// ノードの値を増加させる関数
void increment(node* node, int diff) {
    if (node->left != NULL) {
        node->left->data = node->left->data + diff;
        // 再帰的に木をたどる
        increment(node->left, diff);
    }
    else if (node->right != NULL) {
        node->right->data = node->right->data + diff;
        increment(node->right, diff);
    }
}

// 中間順走査（Inorder Traversal）で表示
void printInorder(node* node) {
    if (node == NULL)
        return;
    printInorder(node->left);
    cout << node->data << " ";
    printInorder(node->right);
}

int main() {
    node *root = new node(50);
    root->left = new node(7);
    root->right = new node(2);
    root->left->left = new node(3);
    root->left->right = new node(5);
    root->right->left = new node(1);
    root->right->right = new node(30);
    cout << "Before conversion: " << endl;
    printInorder(root);
    convert_Btree(root);
    cout << "\nAfter conversion: " << endl;
    printInorder(root);
    return 0;
}

出力結果

Before conversion:
3 7 5 50 1 2 30
After conversion:
14 19 5 50 1 31 30

出力の解説

変換後の中間順走査の結果「14 19 5 50 1 31 30」を見ると、すべての内部ノードでChildren Sum Propertyが成立していることが確認できます。

• ルートノード：19 ＋ 31 ＝ 50 ✓
• 左の子ノード：14 ＋ 5 ＝ 19 ✓
• 右の子ノード：1 ＋ 30 ＝ 31 ✓

また、変換によって値が減少したノードは存在せず、木の構造も一切変更されていないため、問題の制約を満たした正しい変換になっています。

まとめ

このように、再帰を用いて部分木ごとにボトムアップで処理を行うことで、値の増加のみを許可するという制約のもとでも、任意の二分木をChildren Sum Propertyを満たす木へ変換できます。基本の走査は各ノードを一度ずつ訪問しますが、increment関数が経路上のノードを追加で更新するため、木が偏っている最悪ケースでは計算量がO(n²)になる点には注意してください。