C++で解説：二分木の中からBST条件を満たす部分木の最大合計を求める方法

はじめに

このチュートリアルでは、二分木（Binary Tree）の中から「二分探索木（BST）」の条件も満たす部分木を探し出し、そのノード値の合計が最大になる部分木を求めるプログラムについて解説します。

入力として二分木が与えられ、その中に存在する部分木のうちBSTの性質を満たすものの合計値を計算し、最大のものを出力するのが目的です。

アルゴリズムの考え方

この問題を効率的に解く鍵は、各ノードを再帰的に走査しながら、次の情報を持ち回ることです。

• 部分木内の最大値（max）
• 部分木内の最小値（min）
• その部分木がBSTかどうか（isBST）
• 部分木のノード値の合計（sum）
• それまでに見つかった最大合計（currmax）

あるノードについて、左右の部分木がどちらもBSTであり、かつ「左部分木の最大値 ＜ 自分の値 ＜ 右部分木の最小値」という条件が成り立てば、そのノードを根とする部分木もBSTであると判定できます。この場合、左右の部分木の合計に自分の値を加えたものが新たな候補となり、これまでの最大合計と比較して更新を行います。

条件を満たさない場合は、その部分木はBSTではないため合計の候補にはせず、これまでの最大合計をそのまま引き継ぎます。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
// 二分木のノードを定義
struct Node {
    struct Node* left; struct Node* right; int data;
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
struct Info {
    int max;
    int min;
    bool isBST;
    int sum;
    int currmax;
};
Info MaxSumBSTUtil(struct Node* root, int& maxsum) {
    if (root == NULL) return { INT_MIN, INT_MAX, true, 0, 0 };
    if (root->left == NULL && root->right == NULL) {
        maxsum = max(maxsum, root->data);
        return { root->data, root->data, true, root->data, maxsum };
    }
    Info L = MaxSumBSTUtil(root->left, maxsum);
    Info R = MaxSumBSTUtil(root->right, maxsum);
    Info BST;
    if (L.isBST && R.isBST && L.max < root->data && R.min > root->data) {
        BST.max = max(root->data, max(L.max, R.max));
        BST.min = min(root->data, min(L.min, R.min));
        maxsum = max(maxsum, R.sum + root->data + L.sum);
        BST.sum = R.sum + root->data + L.sum;
        BST.currmax = maxsum;
        BST.isBST = true;
        return BST;
    }
    BST.isBST = false;
    BST.currmax = maxsum;
    BST.sum = R.sum + root->data + L.sum;
    return BST;
}
int MaxSumBST(struct Node* root) {
    int maxsum = INT_MIN;
    return MaxSumBSTUtil(root, maxsum).currmax;
}
int main() {
    struct Node* root = new Node(5);
    root->left = new Node(14);
    root->right = new Node(3);
    root->left->left = new Node(6);
    root->right->right = new Node(7);
    root->left->left->left = new Node(9);
    root->left->left->right = new Node(1);
    cout << MaxSumBST(root);
    return 0;
}

出力

10

コードの解説

サンプルの二分木では、根の値5、左の子14、右の子3という構成になっており、さらに14の左に6、3の右に7、6の左に9・右に1が接続されています。

このうち「3を根とし、右に7を持つ部分木」はBSTの条件を満たし、合計は3 + 7 = 10 となります。一方、「6を根とする部分木」は左の子9が自分より大きいためBSTではなく、候補から除外されます。したがって、最大合計は10となり、これが正解として出力されます。

計算量

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量はO(N)（Nはノード数）です。再帰呼び出しに伴うスタック領域として、木の高さに比例したO(H)の空間が必要になります。