【C++】二分木にサイズ2以上の重複する部分木が存在するかを判定する方法

問題の概要

二分木が与えられたとき、その木の中にサイズ2以上の同一の部分木(重複部分木)が存在するかどうかを判定するのが本記事のテーマです。例として、次のような二分木を考えてみます。

この木には、サイズ2の同一の部分木が2つ含まれています。このように、同じ構造・同じノード値を持つ部分木が複数存在するかどうかを効率よくチェックする必要があります。

アプローチ:シリアライズとハッシュの活用

この問題は、部分木のシリアライズ(文字列化)とハッシュテーブルを組み合わせることで効率的に解くことができます。基本的なアイデアは以下の通りです。

• 各ノードから再帰的に部分木を文字列としてシリアライズし、ハッシュ集合(unordered_set)に登録していく。
• NULL の子ノードはマーカー($)で表現することで、木の構造の違いも文字列に正確に反映させる。
• ある部分木のシリアライズ結果が、すでに集合に存在しており、かつそれが葉1個だけの部分木ではない(=サイズ2以上である)場合、重複する部分木が見つかったことになるため、空文字列を返して検出を通知する。

ここでポイントとなるのは、シリアライズ後の文字列長が3より大きいことを判定条件に使う点です。葉1個の部分木(例:D$$)は長さがちょうど3になるため、「長さ > 3」であれば必ず2ノード以上の部分木であると判別できます。

C++による実装例

#include <iostream>
#include <unordered_set>
using namespace std;
const char MARKER = '$';
struct Node {
    public:
    char key;
    Node *left, *right;
};
Node* getNode(char key) {
    Node* newNode = new Node;
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}
unordered_set<string> subtrees;
string duplicateSubtreeFind(Node *root) {
    string res = "";
    if (root == NULL) // 現在のノードがNULLの場合は $ を返す
        return res + MARKER;
    string l_Str = duplicateSubtreeFind(root->left);
    if (l_Str.compare(res) == 0)
        return res;
    string r_Str = duplicateSubtreeFind(root->right);
    if (r_Str.compare(res) == 0)
        return res;
    res = res + root->key + l_Str + r_Str;
    // サイズ2以上の部分木が既に登録されている場合は重複あり → 空文字列を返す
    if (res.length() > 3 && subtrees.find(res) != subtrees.end())
        return "";
    subtrees.insert(res);
    return res;
}
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');
    string str = duplicateSubtreeFind(root);
    if(str.compare("") == 0)
        cout << "It has duplicate subtrees of size more than 1";
    else
        cout << "It has no duplicate subtrees of size more than 1";
}

重複が検出されると空文字列が返され、それが再帰の呼び出し元へ順に伝播することで、main() 側で重複の有無を最終的に判断できる仕組みになっています。

実行結果

It has duplicate subtrees of size more than 1

計算量

• 時間計算量: 最悪 O(n²)(各ノードで部分木のシリアライズ文字列を構築・比較するため)
• 空間計算量: 最悪 O(n²)(すべての部分木のシリアライズ文字列をハッシュ集合に保存するため)