C++로 구현하는 n-ary 트리 미러 변환

문제 정의

각 노드가 가변적인 개수의 자식 노드를 가질 수 있는 n-ary 트리가 주어졌을 때, 이 트리 전체를 좌우가 뒤집힌 미러(mirror) 트리로 변환하는 문제입니다.

예시

다음과 같은 n-ary 트리가 있다고 가정해 보겠습니다.

이 트리를 미러링하면 아래와 같은 형태가 됩니다.

C++ 구현 코드

아래 코드는 재귀적으로 각 노드를 방문한 후, 해당 노드의 자식들이 저장된 벡터(vector)를 뒤집는 방식으로 미러 트리를 생성합니다.

#include <bits/stdc++.h>
using namespace std;
struct node {
   int data;
   vector<node *>child;
};
node *newNode(int x) {
   node *temp = new node;
   temp->data = x;
   return temp;
}
void mirrorTree(node * root) {
   if (root == NULL) {
      return;
   }
   int n = root->child.size();
   if (n < 2) {
      return;
   }
   for (int i = 0; i < n; i++) {
      mirrorTree(root->child[i]);
   }
   reverse(root->child.begin(), root->child.end());
}
void printTree(node * root) {
   if (root == NULL) {
      return;
   }
   queue<node *>q;
   q.push(root);
   int level = 0;
   while (!q.empty()) {
      int n = q.size();
      ++level;
      cout << "Level " << level << ": ";
      while (n > 0) {
         node * p = q.front();
         q.pop();
         cout << p->data << " ";
         for (int i=0; i<p->child.size(); i++) {
            q.push(p->child[i]);
         }
         n--;
      }
      cout << endl;
   }
}
int main() {
   node *root = newNode(20);
   (root->child).push_back(newNode(10));
   (root->child).push_back(newNode(15));
   (root->child[0]->child).push_back(newNode(1));
   (root->child[0]->child).push_back(newNode(2));
   (root->child[0]->child).push_back(newNode(3));
   (root->child[1]->child).push_back(newNode(4));
   cout << "Tree traversal before mirroring\n";
   printTree(root);
   mirrorTree(root);
   cout << "\nTree traversal after mirroring\n";
   printTree(root);
   return 0;
}

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

출력 결과

Tree traversal before mirroring
Level 1: 20
Level 2: 10 15
Level 3: 1 2 3 4
Tree traversal after mirroring
Level 1: 20
Level 2: 15 10
Level 3: 4 3 2 1

알고리즘 동작 원리

• 재귀 순회: 루트 노드부터 시작해 각 자식 노드에 대해 mirrorTree 함수를 재귀적으로 호출합니다.
• 자식 수 확인: 자식이 2개 미만인 노드는 뒤집어도 결과가 동일하므로 즉시 반환합니다.
• 자식 순서 반전: 모든 하위 트리의 변환이 완료되면 reverse() 함수를 사용해 해당 노드의 자식 벡터를 뒤집습니다.

이 알고리즘은 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(N)이며, 재귀 호출 깊이는 트리의 높이에 비례하므로 공간 복잡도는 O(H)입니다.