C++で二分木における最大部分木の合計を求める方法

この問題では、二分木（バイナリツリー）が与えられます。私たちのタスクは、木の中で最も大きな合計値を持つ部分木を見つけることです。

問題の概要

二分木には正の値と負の値が混在しています。その中から、ノードの合計が最大になる部分木を特定する必要があります。

例で問題を理解しよう

出力： 13

説明：

• 左部分木の合計：7
• 右部分木の合計：1
• 木全体の合計：13

このように、根を含む木全体の合計である「13」が最大の部分木の合計となります。

解法のアプローチ

この問題を解くためには、後順走査（ポストオーダー走査）を利用します。手順は以下の通りです。

1. 左部分木と右部分木それぞれのノードの合計を再帰的に計算します。
2. 現在のノードについて、「現在のノードを含む部分木の合計」が「左部分木または右部分木の合計」より大きいかどうかを確認します。
3. 葉ノードから根ノードへと辿りながら、各段階での最大の合計を記録していきます。

後順走査を使うことで、子ノードの合計が確定した後に親ノードの合計を計算できるため、各ノードを一度だけ訪問する効率的な処理が可能になります。

ソリューションの実装プログラム

C++コード例

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
};

Node* newNode(int key) {
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

int calcSumTreeSumRec(Node* root, int& ans) {
    if (root == NULL)
        return 0;
    int currSum = root->key + calcSumTreeSumRec(root->left, ans) + calcSumTreeSumRec(root->right, ans);
    ans = max(ans, currSum);
    return currSum;
}

int calcMaxSubTreeSum(Node* root)
{
    if (root == NULL)
        return 0;
    int ans = -100;
    calcSumTreeSumRec(root, ans);
    return ans;
}

int main() {

    Node* root = newNode(5);
    root->left = newNode(-4);
    root->right = newNode(4);
    root->left->left = newNode(3);
    root->left->right = newNode(8);
    root->right->left = newNode(-5);
    root->right->right = newNode(2);

    cout<<"The largest subtree sum is "<<calcMaxSubTreeSum(root);
    return 0;
}

出力結果

The largest subtree sum is 13

コードのポイント

• calcSumTreeSumRec 関数は再帰的に各ノードの部分木の合計を計算し、その都度これまでの最大値 ans を更新します。
• 初期値を負の数に設定することで、すべてのノードが負の値の場合にも正しく動作します。
• 計算量は各ノードを一度だけ訪問するため O(N)、空間計算量は再帰の深さ分の O(H)（Hは木の高さ）となります。