【C++】部分木がBSTでもある二分木における最大部分木合計の求め方

問題概要

この問題では、二分木 BT が与えられ、「その部分木自身も二分探索木（BST）である」という条件を満たす部分木の中から、ノード値の合計が最大となるものを見つけるプログラムを作成します。

二分木（Binary Tree）とは

二分木とは、各ノードが最大2つの子ノードを持つことができる特殊な木構造です。

二分探索木（BST）とは

二分探索木とは、すべてのノードが以下の性質を満たす木のことです。

• 左部分木のキー値は、親（ルート）ノードのキー値より小さい。
• 右部分木のキー値は、親（ルート）ノードのキー値以上である。

入出力例

入力：

出力：

32

説明：この木には BST として成立している部分木が2つ存在します。それぞれの合計値は以下の通りです。

7 + 3 + 22 = 32
6 + 5 + 17 = 28
最大値 = 32

解法アプローチ

最もシンプルな解き方は、木構造を走査しながら、各ノードにおいてその子ノードたちが二分探索木を形成できるかどうかを確認していく方法です。BST を構成するすべてのノードの合計を計算し、最終的に得られた BST の合計値の中から最大のものを返します。

この処理は再帰的に実装できます。各ノードについて「部分木内の最小値・最大値」「BST かどうかの判定」「合計値」をボトムアップで親ノードへ伝播させることで、木全体を一度の走査（時間計算量 O(N)）で効率よく解くことが可能です。

C++による実装例

以下は、この解法の動作を示すサンプルプログラムです。

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

int findMax(int a, int b){
    if(a > b)
        return a;
    return b;
}

int findMin(int a, int b){
    if(a > b)
        return b;
    return a;
}

struct Node {
    struct Node* left;
    struct Node* right;
    int data;
    Node(int data){
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

struct treeVal{
    int maxVal;
    int minVal;
    bool isBST;
    int sum;
    int currMax;
};

treeVal CalcBSTSumTill(struct Node* root, int& maxsum){
    if (root == NULL)
        return { -10000, 10000, true, 0, 0 };
    if (root->left == NULL && root->right == NULL) {
        maxsum = findMax(maxsum, root->data);
        return { root->data, root->data, true, root->data, maxsum };
    }
    treeVal LeftSTree = CalcBSTSumTill(root->left, maxsum);
    treeVal RightSTree = CalcBSTSumTill(root->right, maxsum);
    treeVal currTRee;
    if (LeftSTree.isBST && RightSTree.isBST && LeftSTree.maxVal < root->data && RightSTree.minVal > root->data) {
        currTRee.maxVal = findMax(root->data, findMax(LeftSTree.maxVal, RightSTree.maxVal));
        currTRee.minVal = findMin(root->data, findMin(LeftSTree.minVal, RightSTree.minVal));
        maxsum = findMax(maxsum, RightSTree.sum + root->data + LeftSTree.sum);
        currTRee.sum = RightSTree.sum + root->data + LeftSTree.sum;
        currTRee.currMax = maxsum;
        currTRee.isBST = true;
        return currTRee;
    }
    currTRee.isBST = false;
    currTRee.currMax = maxsum;
    currTRee.sum = RightSTree.sum + root->data + LeftSTree.sum;
    return currTRee;
}

int CalcMaxSumBST(struct Node* root){
    int maxsum = -10000;
    return CalcBSTSumTill(root, maxsum).currMax;
}

int main(){
    struct Node* root = new Node(10);
    root->left = new Node(12);
    root->left->right = new Node(7);
    root->left->right->left = new Node(3);
    root->left->right->right = new Node(22);
    root->right = new Node(6);
    root->right->left = new Node(5);
    root->right->left->right = new Node(17);
    cout << "The maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST is " << CalcMaxSumBST(root);
    return 0;
}

出力結果

The maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST is 32

このように、BST の条件を満たす部分木の中で最大となる合計値「32」が正しく求められていることがわかります。