C++で二分木の各レベルにおける非葉ノードの合計の最大値を求める方法

この記事では、二分木が与えられたときに、すべてのレベルの中から非葉ノード（子ノードを持つノード）の合計が最大となるレベルの合計値を求めるC++プログラムの作成方法を解説します。

問題の概要

二分木の各レベルごとに非葉ノードのデータ値の合計を計算し、その中で最も大きい合計値を出力します。

入力例

出力例

9

解説

各レベルにおける非葉ノードの合計は以下のようになります。

レベル1: 4
レベル2: 1 + 2 = 3
レベル3: 9（4と7は葉ノードのため対象外）
レベル4: 0

この結果から、最大の合計値は「9」であることがわかります。

解決のアプローチ

この問題を解くには、二分木に対してレベル順走査（幅優先探索：BFS）を行い、各レベルの非葉ノードの合計を求めて、その最大値を記録していく必要があります。

具体的な手順は次のとおりです。

1. キューを使ってレベル順にノードを処理します。
2. 各ノードについて、左の子または右の子を持っているかどうかを確認します。子を持つノード（＝非葉ノード）であれば、その値を現在のレベルの合計に加算します。
3. レベル内のすべてのノードを処理したら、その合計がこれまでの最大値 maxSum を上回っていれば更新します。
4. すべてのレベルの走査が終わった時点の maxSum が答えとなります。

なお、空の木（NULL）が渡された場合は0を返すようにしています。

実装例

上記の解法を実装したプログラムは以下のとおりです。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
int maxLevelSum(struct Node* root){
    if (root == NULL)
        return 0;
    int maxSum = root->data;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int count = q.size();
        int levelSum = 0;
        while (count--) {
            Node* temp = q.front();
            q.pop();
            // 子を持つノード（非葉ノード）のみ合計に加算
            if (temp->left != NULL || temp->right != NULL)
                levelSum = levelSum + temp->data;
            if (temp->left != NULL)
                q.push(temp->left);
            if (temp->right != NULL)
                q.push(temp->right);
        }
        maxSum = max(levelSum, maxSum);
    }
    return maxSum;
}
struct Node* insertNode(int data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
int main() {
    struct Node* root = insertNode(6);
    root->left = insertNode(1);
    root->right = insertNode(2);
    root->left->left = insertNode(4);
    root->left->right = insertNode(7);
    root->right->right = insertNode(9);
    root->right->right->left = insertNode(5);
    cout<<"The maximum sum of all non-leaf nodes at a level of the binary tree is "<<maxLevelSum(root);
    return 0;
}

実行結果

The maximum sum of all non-leaf nodes at a level of the binary tree is 9

計算量について

このアルゴリズムでは、各ノードを一度だけ訪問するため、時間計算量は O(N)（Nはノード数）、キューに格納されるノード数に比例して空間計算量も O(N) となります。木全体を効率よく走査できるため、大きな二分木に対しても実用的な手法です。