隣接するレベルのノードを同時に選べない二分木の最大合計をC++で求める方法

本記事では、正の整数のみで構成された二分木が与えられたとき、隣接するレベルのノードを同時に合計に含めないという条件を満たす最大合計を求めるプログラムを、C++で解説します。

問題の内容

ここで扱うのは、木の中からいくつかのノードを選び、その値の合計を最大化する問題です。ただし、選んだノードが隣接する2つのレベル（親子関係にある階層）にまたがることはできません。あるレベルのノードを合計に採用したら、その直上・直下のレベルのノードは一切使用できない、という制約があります。

具体例で理解する

次のような二分木を例に考えてみます。

        5
       / \
      2   10
     / \    \
    4   6    9

考えられる選び方は、主に次の2通りです。

• ルート（レベル1）を起点にする場合： 5 + 4 + 6 + 9 = 24
• ルートの子（レベル2）を起点にする場合： 2 + 10 = 12

両者を比較すると、この木における最大合計は 24 であることがわかります。

解決アプローチ

「隣接するノードを含めない」という制約を満たすために、次の2つのケースをそれぞれ計算し、大きい方を答えとします。

• ルートノード（レベル1）から始まる合計
• ルートの子ノード（レベル2）から始まる合計

重要なのは、あるノードを採用した場合、次に選べるのは必ず孫ノード（2つ下のレベル）だという点です。この性質を利用し、各ノードを起点とした最大合計を再帰的に求めていきます。

具体的には、次の2つの関数を組み合わせて実現します。

• findSumFromNode()：指定したノード自身の値に、そのすべての孫ノード以降から得られる最大合計を加えた値を返す
• getMaxSum()：「自分自身を起点とする場合」と「左右の子をそれぞれ起点とする場合」のうち大きい方を返す

C++による実装例

上記のアイデアを実装したプログラムがこちらです。

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node* left, *right;
    Node(int item){
        data = item;
    }
};
int getMaxSum(Node* root);
int findSumFromNode(Node* root){
    if (root == NULL)
        return 0;
    int sum = root->data;
    if (root->left != NULL){
        sum += getMaxSum(root->left->left);
        sum += getMaxSum(root->left->right);
    }
    if (root->right != NULL){
        sum += getMaxSum(root->right->left);
        sum += getMaxSum(root->right->right);
    }
    return sum;
}
int getMaxSum(Node* root){
    if (root == NULL)
        return 0;
    return max(findSumFromNode(root), (findSumFromNode(root->left) + findSumFromNode(root->right)));
}
int main(){
    Node* root = new Node(5);
    root->left = new Node(2);
    root->right = new Node(10);
    root->left->left = new Node(4);
    root->left->right = new Node(6);
    root->right->right = new Node(9);
    cout<<"隣接レベルを含まないツリーの最大合計は "<<getMaxSum(root);
    return 0;
}

出力

隣接レベルを含まないツリーの最大合計は 24

補足：計算量について

この実装はシンプルで理解しやすい反面、同じ部分木に対する計算が何度も繰り返されるため、木の形状によっては非効率になることがあります。各ノードの計算結果をハッシュマップなどにキャッシュしてメモ化することで、時間計算量をO(N)程度まで改善できます。実務で大きな木を扱う場合は、メモ化の導入を検討するとよいでしょう。