C++で解く最大二分木II：値の挿入アルゴリズムを徹底解説

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

本記事では、C++を用いて「最大二分木II」の問題を解く方法を詳しく解説します。

まず、最大木（Maximum Tree）についておさらいしましょう。最大木とは、すべてのノードが、その部分木に含まれる他のどの値よりも大きな値を持つ二分木のことです。

construct() メソッドの定義

リストAから根ノードを構築する construct() メソッドがあると仮定します。このメソッドは以下のように動作します。

• リストAが空の場合、null を返します。
• それ以外の場合、A[i] をリストAの最大要素とし、値 A[i] を持つ根ノードを作成します。
• 根の左の子は construct([A[0], A[1], ..., A[i-1]]) となります。
• 根の右の子は construct([A[i+1], A[i+2], ..., A[n-1]]) となります（n は A の長さ）。
• 根を返します。

問題の概要

ここで重要なポイントとして、リストAそのものは与えられず、根ノード root = construct(A) のみが渡されます。さらに、BはAのコピーに値 val を末尾に追加したリストであり、Bのすべての値は一意であることが保証されています。私たちのタスクは、construct(B) を実行して新しい木を構築することです。

例えば、val が 5 で、入力の木が次のような場合を考えてみましょう。

このとき、出力される木は以下のようになります。

解法のアプローチ

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

• solve() という再帰メソッドを定義します。このメソッドは root と val を引数に取ります。
• 木が空の場合、値 val を持つ新しいノードを作成し、そのノードを返します。
• root の値が val より小さい場合：
  
  • temp := 値が val の新しいノード
  • temp の左の子 := root
  • temp を返します
• root の右の子 := solve(root の右の子, val)
• root を返します。

このアルゴリズムの鍵となるのは、追加される値 val が必ずリストBの末尾に加わるという点です。そのため、val は木の右側の経路にのみ挿入されればよいことになります。走査中に現在のノードの値が val より小さくなった時点で、val がその位置の新しい親ノードとなり、元の部分木全体がその左の子へ移動します。これにより、最大木の性質が完全に保たれたまま挿入が完了します。

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 tree_level_trav(TreeNode*root){
    if (root == NULL) return;
    cout << "[";
    queue<TreeNode *> q;
    TreeNode *curr;
    q.push(root);
    q.push(NULL);
    while (q.size() > 1) {
        curr = q.front();
        q.pop();
        if (curr == NULL){
            q.push(NULL);
        }
        else {
            if(curr->left)
               q.push(curr->left);
            if(curr->right)
               q.push(curr->right);
            if(curr == NULL || curr->val == 0){
               cout << "null" << ", ";
            }else{
               cout << curr->val << ", ";
            }
        }
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if(!root)return new TreeNode(val);
        if(root->val < val){
            TreeNode* temp = new TreeNode(val);
            temp->left = root;
            return temp;
        }
        root->right = insertIntoMaxTree(root->right, val);
        return root;
    }
};
main(){
    vector<int> v = {4,1,3,NULL,NULL,2};
    TreeNode *root = make_tree(v);
    Solution ob;
    tree_level_trav(ob.insertIntoMaxTree(root, 5));
}

入力例

[4,1,3,null,null,2]
5

出力例

[5, 4, 1, 3, null, null, 2]

まとめ

最大二分木への値の挿入は、再帰的に右側の経路を辿るだけで実現できます。計算量は木の高さに依存し、最悪の場合でも O(n) に収まるため、非常に効率的なアルゴリズムです。「val は常にリストの末尾に追加される」という前提条件を活かすことで、木全体を再構築することなく最小限の変更で目的を達成できる点が、この問題の面白いところです。