C++で二分木が同型（アイソモーフィック）かどうかを判定する方法

二分木では、各ノードが「左の子」と「右の子」という2つの子ノードを持ちます。ここでは、2つの二分木が与えられたとき、一方の木を左右反転（フリップ）することでもう一方の木が得られるかどうかを判定する問題を解説します。

一方の木を反転することでもう一方の木と同じ構造が得られる場合、その2つの木は「同型（アイソモーフィック）」であると定義されます。

具体例

入力1

出力

Isomorphic（同型）

説明：Tree-2はTree-1を左右反転することで得られるため、この2つの木は同型です。

解き方のアプローチ

この問題は再帰的なアプローチで効率的に解くことができます。ブール型の関数を用意し、両方の木のルートノードを順にチェックしていきます。両方の木のルートが空（NULL）の場合はtrueを返し、両方のルートが同じデータを持つかどうかを再帰的に確認します。その後、左側と右側の部分木についても同様に再帰的にチェックを行います。

• 2つの二分木のノードを作成します。
• ブール関数 isIsomorphicTree(node *r1, node *r2) は、2つの木のルートを受け取り、木が同型であるかどうかを返します。
• 木が空、またはノードを1つも持たない場合はtrueを返します。
• 部分木が反転されていない場合と、両方が反転されている場合のいずれかが成立すればtrueを返します。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
struct treenode {
    int data;
    treenode * left;
    treenode * right;
};
struct treenode * createNode(int d) {
    struct treenode * root = new treenode;
    root -> data = d;
    root -> left = NULL;
    root -> right = NULL;
    return root;
}
bool isIsomorphicTree(treenode * r1, treenode * r2) {
    if (r1 == NULL and r2 == NULL) {
        return true;
    }
    if (r1 == NULL or r2 == NULL) {
        return false;
    }
    return (r1 -> data == r2 -> data && ((isIsomorphicTree(r1 -> left, r2 -> right) && isIsomorphicTree(r1 -> right, r2 -> left)) || (isIsomorphicTree(r1 -> left, r2 -> left) && isIsomorphicTree(r1 -> right, r2 -> right))));
}
int main() {
    struct treenode * r1 = createNode(1);
    r1 -> left = createNode(2);
    r1 -> right = createNode(3);
    r1 -> left -> left = createNode(4);
    r1 -> left -> right = createNode(5);
    r1 -> right -> left = createNode(6);
    r1 -> left -> right -> left = createNode(7);
    r1 -> left -> right -> right = createNode(8);
    struct treenode * r2 = createNode(1);
    r2 -> left = createNode(3);
    r2 -> right = createNode(2);
    r2 -> right -> left = createNode(4);
    r2 -> right -> right = createNode(5);
    r2 -> left -> right = createNode(6);
    r2 -> right -> right -> left = createNode(8);
    r2 -> right -> right -> right = createNode(7);
    if (isIsomorphicTree(r1, r2)) {
        cout << "Isomorphic" << endl;
    } else {
        cout << "Not an Isomorphic" << endl;
    }
    return 0;
}

上記のコードを実行すると、以下の出力が得られます。

出力

Isomorphic

説明：一方の木を左右反転することでもう一方の木が得られるため、この2つの木は同型です。