C++でn分木（N-aryツリー）をミラー反転する方法

問題の概要

各ノードが可変個の子ノードを持つ木（n分木）が与えられたとき、その木をミラー（左右反転した木）に変換する方法を解説します。ミラー化とは、各ノードの子ノードの並び順を左右逆にすることを指します。

ミラー化の例

例として、次のようなn分木を考えます。

この木をミラー化すると、以下のように反転されます。

アルゴリズムの考え方

ミラー化は再帰を使うとシンプルに実装できます。手順は以下のとおりです。

手順

1. ノードがNULLの場合は何もせずに終了します。
2. 子ノードが1つ以下の場合、反転しても変化がないためそのまま返します。
3. 各子ノードに対して再帰的にミラー化を適用します。
4. 最後に、そのノードが持つ子ノードのリスト（vector）を反転します。

C++での実装例

以下は、木をレベル順（BFS）で出力する機能も含めた完全なサンプルコードです。

#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

出力を見ると、ミラー化によって各レベルの子ノードの並びが反転していることが確認できます（10 15 → 15 10、1 2 3 4 → 4 3 2 1）。

計算量

時間計算量： O(N)（Nは木のノード総数。各ノードを1度ずつ処理します）
空間計算量： O(N)（再帰呼び出しのスタックと、出力用のキューが主な要因です）