C++で生成可能なすべての完全二分木を列挙する方法

問題の概要

完全二分木（フルバイナリツリー）とは、すべてのノードが子をちょうど0個または2個持つ二分木のことです。この問題では、N個のノードから構成されるすべての完全二分木のリストを求めます。返される木の各ノードの値は0とし、木の並び順は問われません。例えば、入力が7の場合、以下のような木が生成されます。

なお、完全二分木のノード総数は必ず奇数（葉がn個なら全体で2n−1個）になるため、Nが偶数の場合は条件を満たす木が存在しない点にも注意が必要です。

解法のアプローチ

この問題は、再帰とメモ化（計算結果のキャッシュ）を組み合わせることで効率的に解くことができます。具体的な手順は以下の通りです。

• 整数をキー、TreeNodeのベクトルを値とするマップmを定義します。
• Nを引数として受け取るメソッドallPossibleFBT()を定義します。
• Nが1の場合、値0のノードを1つだけ持つ木を作成して返します。
• マップmにキーNが既に存在する場合は、計算済みのm[N]を返します（メモ化）。未計算の場合は、配列tempを用意し、req := N − 1 とします。
• leftを1からreq − 1までループします。
  • right := req − left とします。
  • leftが2、またはrightが2の場合は次の反復へスキップします（子を1個だけ持つノードは完全二分木に現れないため）。
  • leftPart := allPossibleFBT(left)、rightPart := allPossibleFBT(right) として、左右の部分木の候補を再帰的に取得します。
  • jを0からleftPartのサイズ−1まで、kを0からrightPartのサイズ−1までループします。
    • 値0を持つ新しいノードrootを作成します。
    • rootの左の子にleftPart[j]を、右の子にrightPart[k]を設定します。
    • rootをansに追加します。
• 最後に m[N] := ans を設定して返します。

C++での実装例

以下の実装例を見ると、より理解が深まります。

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
        int val;
        TreeNode *left, *right;
        TreeNode(int data){
            val = data;
            left = right = NULL;
        }
};
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:
    map < int, vector <TreeNode*> > m;
    vector<TreeNode*> allPossibleFBT(int N) {
        if(N == 1){
            vector <TreeNode*> temp;
            TreeNode *n = new TreeNode(1);
            n->left = new TreeNode(0);
            n->right = new TreeNode(0);
            temp.push_back(n);
            return temp;
        }
        if(m.count(N))return m[N];
        vector <TreeNode*> ans;
        int required = N - 1;
        for(int left = 1; left < required; left++){
            int right = required - left;
            if(left == 2 || right == 2)continue;
            vector <TreeNode*> leftPart = allPossibleFBT(left);
            vector <TreeNode*> rightPart = allPossibleFBT(right);
            for(int j = 0; j < leftPart.size(); j++){
                for(int k = 0; k < rightPart.size(); k++){
                    TreeNode* root = new TreeNode(1);
                    root->left = leftPart[j];
                    root->right = rightPart[k];
                    ans.push_back(root);
                }
            }
        }
        return m[N] = ans;
    }
};
main(){
    vector<TreeNode*> v;
    Solution ob;
    v = (ob.allPossibleFBT(7)) ;
    for(TreeNode *t : v){
        tree_level_trav(t);
    }
}

入力

7

出力

[1, 1, 1, null, null, 1, 1, null, null, 1, 1, null, null, null, null]
[1, 1, 1, null, null, 1, 1, 1, 1, null, null, null, null, null, null]
[1, 1, 1, 1, 1, 1, 1, null, null, null, null, null, null, null, null]
[1, 1, 1, 1, 1, null, null, null, null, 1, 1, null, null, null, null]
[1, 1, 1, 1, 1, null, null, 1, 1, null, null, null, null, null, null]

このように、根の左右に割り当てるノード数を再帰的に組み合わせながら、メモ化によって重複計算を避けることで、すべての完全二分木を効率的に列挙することができます。