C++로 두 이진 트리가 동형(Isomorphic)인지 확인하는 방법

이진 트리(binary tree)에서 각 노드는 왼쪽 자식과 오른쪽 자식, 최대 두 개의 자식 노드를 가집니다. 두 개의 이진 트리가 주어졌을 때, 한 트리의 좌우를 뒤집어(flip) 다른 트리를 만들 수 있는지 확인하는 것이 이 글의 목표입니다.

한 트리를 좌우로 뒤집어서 다른 트리와 동일한 구조를 얻을 수 있다면, 두 트리는 동형(Isomorphic)이라고 합니다.

예제

입력-1

출력: Isomorphic

설명: Tree-1을 좌우로 뒤집으면 Tree-2와 같은 구조가 되므로, 두 트리는 동형입니다.

문제 해결 접근 방법

이 문제는 재귀(recursion)를 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 두 트리의 루트 노드부터 시작해, 각 노드에서 두 가지 경우를 모두 검사하는 것입니다.

두 트리의 루트가 모두 NULL(빈 트리)이면 true를 반환합니다.
한쪽만 NULL이면 구조가 다르므로 false를 반환합니다.
두 노드의 데이터 값이 같은지 먼저 확인합니다.
자식 노드에 대해서는 두 가지 경우를 재귀적으로 검사합니다. ① 뒤집지 않은 상태(왼쪽↔왼쪽, 오른쪽↔오른쪽)가 일치하거나, ② 뒤집은 상태(왼쪽↔오른쪽)가 일치하는 경우입니다.

즉, 어떤 서브트리는 그대로 비교하고, 어떤 서브트리는 좌우를 뒤집어 비교했을 때 전체가 일치하면 두 트리는 동형입니다.

알고리즘 단계

두 개의 이진 트리 노드를 생성합니다.
불리언 함수 isIsomorphicTree(node* r1, node* r2)가 두 트리의 루트를 받아 동형 여부를 반환합니다.
트리가 비어 있거나 노드가 없으면 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) {
    // 두 노드가 모두 NULL인 경우
    if (r1 == NULL && r2 == NULL) {
        return true;
    }
    // 한쪽만 NULL인 경우
    if (r1 == NULL || 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

설명: 첫 번째 트리를 좌우로 뒤집으면 두 번째 트리와 동일한 구조를 얻을 수 있으므로, 두 트리는 동형입니다.

시간 복잡도

각 노드 쌍에 대해 뒤집은 경우와 뒤집지 않은 경우를 모두 검사하므로, 시간 복잡도는 O(min(n₁, n₂))입니다. 여기서 n₁과 n₂는 각 트리의 노드 개수입니다.