C++で二分木内の最大BSTサブツリーを求める方法

二分木が与えられたとき、その中に含まれる「最大のBST（二分探索木）サブツリー」を見つけることを考えます。ここで「最大」とは、含まれるノードの数が最も多いサブツリーを指します。

例えば、次のような二分木が入力として与えられた場合を考えてみましょう。

この場合の出力は 3 となります。ハイライトされた部分が、ノード数最大のBSTサブツリーだからです。

解法のアプローチ

この問題は、再帰的に各ノードの情報を収集することで効率的に解けます。具体的には、以下の手順に従います。

• Data という構造体を定義します。この構造体には4つの値を持たせます。sz（サブツリーのノード数）、maxVal（最大値）、minVal（最小値）、そして真偽値のみを保持する ok（そのサブツリーがBSTであるかどうか）です。

• solve(TreeNode* node) 関数を定義します。

• node が NULL の場合は、(0, INT_MAX, INT_MIN, true) で初期化した Data を返します。

• left := solve(node の左の子)

• right := solve(node の右の子)

• Data 型の curr を定義し、curr.ok := false とします。

• node の値が right.minVal 以上の場合は BST 条件を満たさないため、curr を返します。

• node の値が left.maxVal 以下の場合も同様に、curr を返します。

• left.ok と right.ok がどちらも true の場合：

  • curr.sz := 1 + left.sz + right.sz

  • curr.ok := true

  • curr.maxVal := node の値と right.maxVal の最大値

  • curr.minVal := node の値と left.minVal の最小値

• curr.ok が true の場合、ret := max(ret, curr.sz) として答えを更新し、curr を返します。

メインメソッドでは、ret を 0 で初期化し、solve(root) を呼び出した後、ret を返します。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = NULL;
        right = NULL;
    }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        }
        else{
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }
        else{
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
struct Data{
    int sz;
    int maxVal;
    int minVal;
    bool ok;
    Data(){}
    Data(int a, int b, int c, bool d){
        sz = a;
        minVal = b;
        maxVal = c;
        ok = d;
    }
};
class Solution {
public:
    int ret;
    Data solve(TreeNode* node){
        if (!node)
            return Data(0, INT_MAX, INT_MIN, true);
        Data left = solve(node->left);
        Data right = solve(node->right);
        Data curr;
        curr.ok = false;
        if (node->val >= right.minVal) {
            return curr;
        }
        if (node->val <= left.maxVal) {
            return curr;
        }
        if (left.ok && right.ok) {
            curr.sz = 1 + left.sz + right.sz;
            curr.ok = true;
            curr.maxVal = max(node->val, right.maxVal);
            curr.minVal = min(node->val, left.minVal);
        }
        if (curr.ok)
            ret = max(ret, curr.sz);
        return curr;
    }
    int largestBSTSubtree(TreeNode* root){
        ret = 0;
        solve(root);
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {10,5,15,1,8,NULL,7};
    TreeNode *root= make_tree(v);
    cout << (ob.largestBSTSubtree(root));
}

入力

[10,5,15,1,8,null,7]

出力

3

計算量について

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量は O(n) です。また、再帰呼び出しに伴う空間計算量は、木の高さを h とすると O(h) となります。各ノードごとにサブツリーのサイズ・最大値・最小値・BST判定をまとめて返すことで、無駄な再計算を避けながら効率的に答えを求められるのがポイントです。