C++で二分木における親子ノード合計の最大値を求める方法

このチュートリアルでは、二分木（Binary Tree）において「親ノードとその子ノード2つの値の合計」を計算し、その中で最大となる値を見つけるプログラムについて解説します。

具体的には、二分木が与えられたとき、左右両方の子を持つ各ノードについて「親ノード＋左の子＋右の子」の合計を求め、全ノードの中で最も大きい合計値を出力するのが目的です。

アルゴリズムの考え方

この問題は、木を再帰的に走査することで効率よく解くことができます。手順は以下の通りです。

1. 現在のノードがNULLの場合は0を返します。
2. 左部分木に対して再帰的に同じ処理を行い、結果を保持します。
3. 現在のノードが左の子と右の子の両方を持つ場合のみ、「親＋左の子＋右の子」の合計を計算します。
4. これまでの最大値と比較して、より大きい方を記録します。
5. 右部分木に対しても再帰的に処理を行い、最終的な最大値を返します。

なお、子が1つしかないノードや葉ノードは計算対象外となる点に注意してください。このアルゴリズムの計算量はO(n)で、木の全ノードを一度ずつ訪問するだけで済みます。

実装例（C++）

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
// ノードの生成
struct Node* newNode(int n) {
    struct Node* root = new Node();
    root->data = n;
    root->left = root->right = NULL;
    return root;
}
int maxSum(struct Node* root) {
    if (root == NULL)
        return 0;
    int res = maxSum(root->left);
    if (root->left != NULL && root->right != NULL) {
        int sum = root->data + root->left->data + root->right->data;
        res = max(res, sum);
    }
    return max(res, maxSum(root->right));
}
int main() {
    struct Node* root = newNode(15);
    root->left = newNode(16);
    root->left->left = newNode(8);
    root->left->left->left = newNode(55);
    root->left->right = newNode(67);
    root->left->right->left = newNode(44);
    root->right = newNode(17);
    root->right->left = newNode(7);
    root->right->left->right = newNode(11);
    root->right->right = newNode(41);
    cout << maxSum(root);
    return 0;
}

出力結果

91

動作の解説

上記の例では、ノード15・16・17など複数の親子関係が存在します。それぞれの親ノードについて合計を計算すると、例えば以下のようになります。

• ノード15：15 + 16 + 17 = 48
• ノード16：16 + 8 + 67 = 91
• ノード17：17 + 7 + 41 = 65

この中で最も大きいのは91であるため、プログラムは91を出力します。このように再帰的な深さ優先探索を用いることで、簡潔かつ効率的に親子ノード合計の最大値を求めることができます。