Інвертування дерева

Задано масив цілих чисел. Потрібно побудувати з них Бінарне Дерево Пошуку. Якщо вставлюване значення дорівнює значенню поточної вершини, його слід вставляти в праве піддерево.

Реалізуйте метод InvertTree, який інвертує бінарне дерево.

Інвертоване дерево:

Напишіть код відповідно до наступного інтерфейсу:

class TreeNode
{
public:
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Tree
{
public:
  TreeNode *head;
  Tree() : head(NULL) {};

  void Insert(int val); // Вставка числа val в Бінарне Дерево Пошуку

  void InOrder(void); // Виведіть елементи Бінарного Дерева Пошуку при InOrder обході

  void InvertTree(void); // Інвертування Бінарного Дерева Пошуку
};

Ви можете створювати (використовувати) додаткові методи за необхідністю.

Вхідні дані

Перша строка містить число n (1 ≤ n ≤ 100). Друга строка містить n цілих чисел.

Вихідні дані

Побудуйте Бінарне Дерево Пошуку з вхідних даних. Інвертуйте дерево, використовуючи метод InvertTree. Виведіть елементи Бінарного Дерева Пошуку після інвертування, використовуючи метод InOrder.

Приклади