C++で最大二分木を構築する方法：再帰アルゴリズムと実装例を解説

最大二分木（Maximum Binary Tree）とは？

ここでは、すべての要素が一意（重複なし）である整数配列が与えられたとします。この配列から構築される「最大二分木」は、以下のように定義されます。

• 根（ルート）には、配列内の最大値が格納されます。

• 左部分木は、最大値を基準に分割された左側の部分配列から構築された最大二分木です。

• 右部分木は、最大値を基準に分割された右側の部分配列から構築された最大二分木です。

この定義に従って最大二分木を構築します。たとえば、入力が [3,2,1,6,0,5] の場合、構築される木は次の図のようになります。

解き方のアプローチ

この問題は、再帰的な手法を用いて効率的に解くことができます。具体的な手順は以下の通りです。

• solve() というメソッドを定義します。引数として配列と、処理対象範囲の左右インデックス（left・right）を受け取ります。

• left > right の場合、NULL を返します（空の範囲を意味します）。

• maxIndex := left、maxVal := nums[left] として初期化します。

• i を left + 1 から right まで走査し、maxVal < nums[i] であれば maxVal := nums[i]、maxIndex := i と更新します。

• maxVal を値として持つ新しいノードを作成します。

• ノードの左の子 := solve(nums, left, maxIndex - 1)

• ノードの右の子 := solve(nums, maxIndex + 1, right)

• 作成したノードを返します。

メイン処理では、solve(nums, 0, 配列の長さ - 1) の形式で呼び出します。

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;
}
void inord(TreeNode *root){
    if(root != NULL){
        inord(root->left);
        cout << root->val << " ";
        inord(root->right);
    }
}
class Solution {
    public:
    TreeNode* solve(vector <int>& nums, int left, int right){
        if(left>right)return NULL;
        int maxIndex = left;
        int maxVal = nums[left];
        for(int i = left + 1; i <= right; i++){
            if(maxVal < nums[i]){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode* node = new TreeNode(maxVal);
        node->left = solve(nums, left, maxIndex - 1);
        node->right = solve(nums, maxIndex + 1, right);
        return node;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return solve(nums, 0, nums.size() - 1);
    }
};
main(){
    vector<int> v = {4,3,2,7,1,6};
    Solution ob;
    inord(ob.constructMaximumBinaryTree(v));
}

入力

[3,2,1,6,0,5]

出力

4 3 2 7 1 6

※サンプルコードの main 関数では配列 {4,3,2,7,1,6} を使用しており、出力は構築された木の中間順走査（in-order traversal）の結果です。

計算量について

各再帰呼び出しのたびに範囲内の最大値を線形探索するため、最悪ケース（配列が昇順・降順にソートされている場合など）では時間計算量は O(n²) となります。一方、ランダムなデータに対しては平均 O(n log n) 程度で動作します。空間計算量は再帰の深さに依存し、最悪ケースで O(n) です。