กระจกเงาของต้นไม้ n-ary ใน C++

คำชี้แจงปัญหา

ให้ต้นไม้ที่ทุกโหนดมีจำนวนตัวแปรของเด็ก แปลงต้นไม้เป็นมิเรอร์

ตัวอย่าง

ถ้า n-ary tree เป็น −

แล้วกระจกก็คือ −

ตัวอย่าง

#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