C++で二分木の各レベルにおける最大の積を求めるアルゴリズム

問題の概要

正の値と負の値が混在するノードで構成された二分木が与えられたとします。このとき、木の各レベルに存在するノードの値の積を計算し、その中で最大となる値を求める必要があります。

例として、次のような二分木を考えてみましょう。

この木の場合、各レベルの積は以下のように計算できます。

• レベル0の積：4
• レベル1の積：2 × (-5) = -10
• レベル2の積：(-1) × 3 × (-2) × 6 = 36

したがって、この木における最大のレベル積は 36 となります。

解決のアプローチ

この問題は、木をレベル順走査（幅優先探索・BFS）でたどることで効率的に解けます。キューを利用して各レベルのノードをまとめて処理し、レベルごとに積を計算した上で、その最大値を求めます。

具体的な手順は以下の通りです。

1. ルートノードをキューに追加します。
2. キューが空になるまで、以下の処理を繰り返します。
3. 現在のキューのサイズ（＝そのレベルのノード数）を取得します。
4. キューからノードを1つずつ取り出して積に掛け合わせ、存在する子ノードをキューに追加します。
5. そのレベルの積と現在の最大値を比較し、大きい方を結果として更新します。

C++による実装例

#include<iostream>
#include<queue>
using namespace std;
class Node {
    public:
        int data;
    Node *left, *right;
};
Node* getNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
int getMaxLevelProduct(Node* root) {
    if (root == NULL)
        return 0;
    int res = root->data;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int count = q.size();
        int prod = 1;
        while (count--) {
            Node* temp = q.front();
            q.pop();
            prod *= temp->data;
            if (temp->left != NULL)
                q.push(temp->left);
            if (temp->right != NULL)
                q.push(temp->right);
        }
        res = max(prod, res);
    }
    return res;
}
int main() {
    Node* root = getNode(4);
    root->left = getNode(2);
    root->right = getNode(-5);
    root->left->left = getNode(-1);
    root->left->right = getNode(3);
    root->right->left = getNode(-2);
    root->right->right = getNode(6);
    cout << "Maximum level product is " << getMaxLevelProduct(root) << endl;
}

実行結果

Maximum level product is 36

計算量について

このアルゴリズムでは、各ノードをちょうど1回ずつ処理するため、時間計算量は O(n) です。また、キューには最大で木の最下層に存在するノード数が格納されるため、空間計算量も最悪ケースで O(n) となります。