C++で二分木の最大レベル和を求める方法

問題概要

この問題では、正と負の値を含む二分木が与えられます。私たちのタスクは、二分木におけるレベル和の最大値を見つけることです。

問題の説明： 与えられた二分木に対して、各レベルに存在するすべてのノードの値の合計を計算し、その中で最も大きい値を返します。

具体例を使って問題を理解しましょう。

入力：

出力： 5

説明：

レベル1の要素の合計：3
レベル2の要素の合計：-3 + 4 = 1
レベル3の要素の合計：5 - 1 + 6 - 5 = 5

各レベルの合計は「3」「1」「5」となるため、最大のレベル和は 5 となります。

解法アプローチ

この問題を効率的に解くには、レベル順走査（幅優先探索・BFS） を用いて木を走査します。キューを使用することで、レベルごとにノードを処理し、それぞれのレベルの合計を求めることができます。

アルゴリズムの手順

1. ルートが NULL の場合は 0 を返します。
2. キューにルートノードを追加します。
3. キューが空になるまで以下を繰り返します。
   • 現在のキューのサイズ（＝そのレベルのノード数）を取得します。
   • そのレベルのすべてのノードを取り出しながら合計を計算し、子ノードがあれば次のレベルとしてキューに追加します。
   • レベルの合計と現在の最大値を比較し、必要に応じて最大値を更新します。
4. 最終的な最大値を返します。

この手法により、負の値が含まれる場合でも正しく最大レベル和を求められます。計算量は時間・空間ともに O(n)（n はノード数）です。

解法の実装例

以下は、上記のアプローチを実装した C++ プログラムです。

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

struct Node {

    int data;
    struct Node *left, *right;
};

struct Node* newNode(int data){

    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

int findMaxLevelSum(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();
            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;
}

int main(){

    struct Node* root = newNode(3);
    root->left = newNode(-3);
    root->right = newNode(4);
    root->left->left = newNode(5);
    root->left->right = newNode(-1);
    root->right->left = newNode(6);
    root->right->right = newNode(-5);
    cout<<"The sum of level with maximum level sum is "<<findMaxLevelSum(root);
    return 0;
}

出力

The sum of level with maximum level sum is 5

このように、BFS を活用したレベル順走査によって、二分木の各レベルの合計を効率的に計算し、その最大値を簡単に求めることができます。