C++で二分木内の重複するサブツリーをすべて検出する方法

問題の概要

二分木が与えられたとき、その中に重複するサブツリー（部分木）が存在するかどうかを判定する問題を考えてみましょう。例として、次のような二分木を取り上げます。

この木には、サイズ2の同一のサブツリーが2つ存在します。さらに、それぞれのサブツリー内のDに注目すると、BDとBEもまた重複するサブツリーになっています。

解決のアプローチ：木のシリアライズとハッシュ

この問題は、木のシリアライズ（直列化）とハッシュテーブルを組み合わせることで効率的に解決できます。基本的な考え方は以下のとおりです。

• 各サブツリーを間順走査（inorder traversal）で文字列としてシリアライズする
• 空のノードには開き括弧と閉じ括弧を挿入し、木の構造を一意に表現できるようにする
• シリアライズ結果をハッシュテーブルに記録し、同じ文字列が2回以上現れたノードを重複サブツリーの根として検出する

括弧で構造を明示することで、ノードの構成が異なるサブツリーが同じ走査結果を持つことを防ぎ、正確な重複判定が可能になります。

C++による実装例

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;

struct Node {
public:
    char data;
    Node *left, *right;
};

Node* getNode(char key) {
    Node* newNode = new Node;
    newNode->data = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

unordered_set<string> subtrees;

string inorder(Node* node, unordered_map<string, int>& map) {
    if (!node)
        return "";
    string str = "(";
    str += inorder(node->left, map);
    str += to_string(node->data);
    str += inorder(node->right, map);
    str += ")";
    if (map[str] == 1)
        cout << node->data << " ";
    map[str]++;
    return str;
}

void duplicateSubtreeFind(Node *root) {
    unordered_map<string, int> map;
    inorder(root, map);
}

int main() {
    Node *root = getNode('A');
    root->left = getNode('B');
    root->right = getNode('C');
    root->left->left = getNode('D');
    root->left->right = getNode('E');
    root->right->right = getNode('B');
    root->right->right->right = getNode('E');
    root->right->right->left = getNode('D');
    duplicateSubtreeFind(root);
}

実行結果

D E B

コードのポイント

inorder関数は再帰的にサブツリーを走査し、各サブツリーを「(左部分木)(ノードの値)(右部分木)」という形式の文字列に変換します。この文字列がハッシュマップに登録されてから2回目に出現したタイミング（カウントが1のとき）でノードの値を出力することで、重複するサブツリーの根だけを一度ずつ検出できます。

計算量について補足すると、サブツリーごとに文字列を連結してシリアライズするため、最悪の場合の時間計算量はO(n²)となります。ただし、ハッシュを用いることで木全体を1回の走査で処理でき、実用上は十分に高速に動作するのが大きなメリットです。