C++で隣接しない二分木ノードの最大合計を求める方法

このチュートリアルでは、二分木において「互いに隣接しないノード」だけを選んだときのノード値の最大合計を求めるプログラムを、C++を使って解説します。

問題の設定は次のとおりです。二分木が与えられたとき、親子関係にあるノード同士(直接つながっているノード)を同時に選ばないという条件を満たすノードの部分集合の中から、値の合計が最大になるものを見つけることが課題です。

アプローチ:動的計画法とメモ化

この問題は、動的計画法(DP)にメモ化を組み合わせることで効率的に解けます。各ノードに対して、次の2つの選択肢を比較します。

• そのノードを選ぶ場合: ノード自身の値に加えて、孫ノード(子のさらに下のノード)以降の部分木から得られる最大合計を足し合わせます。
• そのノードを選ばない場合: 子ノード以降の部分木から得られる最大合計をそのまま採用します。

この2つの値のうち大きい方が、そのノードを根とする部分木の答えになります。計算結果を map にキャッシュ(メモ化)することで、同じノードを何度も再計算する無駄を省き、計算量を大幅に削減しています。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 二分木のノード構造体
struct node {
    int data;
    struct node *left, *right;
};
struct node* newNode(int data) {
    struct node *temp = new struct node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
int sumOfGrandChildren(node* node);
int getMaxSum(node* node);
int getMaxSumUtil(node* node, map<struct node*, int>& mp);
int sumOfGrandChildren(node* node, map<struct node*, int>& mp){
    int sum = 0;
    if (node->left)
        sum += getMaxSumUtil(node->left->left, mp) + getMaxSumUtil(node->left->right, mp);
    if (node->right)
        sum += getMaxSumUtil(node->right->left, mp) + getMaxSumUtil(node->right->right, mp);
    return sum;
}
// 最大合計を返す
int getMaxSumUtil(node* node, map<struct node*, int>& mp) {
    if (node == NULL)
        return 0;
    if (mp.find(node) != mp.end())
        return mp[node];
    int incl = node->data + sumOfGrandChildren(node, mp);
    int excl = getMaxSumUtil(node->left, mp) + getMaxSumUtil(node->right, mp);
    mp[node] = max(incl, excl);
    return mp[node];
}
int getMaxSum(node* node) {
    if (node == NULL)
        return 0;
    map<struct node*, int> mp;
    return getMaxSumUtil(node, mp);
}
int main() {
    node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->right->left = newNode(4);
    root->right->right = newNode(5);
    root->left->left = newNode(1);
    cout << getMaxSum(root) << endl;
    return 0;
}

実行結果

11

この例の二分木では、値 2・4・5 のノードを選ぶことで合計 11 が得られます。これらのノードは互いに隣接していないため条件を満たし、これが最大の組み合わせとなります。

コードの解説

sumOfGrandChildren 関数

指定したノードの孫ノード(左の子の左右、右の子の左右)から得られる最大合計を再帰的に計算して返します。あるノードを選んだ場合、次に選べるのは孫ノード以降だけであるため、この関数が必要になります。

getMaxSumUtil 関数

メモ化再帰の中核となる関数です。ノードがNULLの場合は0を返し、すでに計算済みのノードはmapから結果を即座に取得します。未計算の場合は「ノードを選ぶ場合(incl)」と「選ばない場合(excl)」をそれぞれ計算し、大きい方をmapに保存して返します。

getMaxSum 関数

エントリポイントとなる関数で、メモ化用のmapを用意して getMaxSumUtil を呼び出します。

計算量

メモ化により各ノードの計算は一度だけ行われるため、ノード数をNとすると時間計算量は O(N) となり、大きな二分木でも効率的に動作します。