Збалансоване Бінарне Дерево

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

Реалізуйте метод IsBalanced, який визначає, чи є дерево збалансованим за висотою. Дерево вважається збалансованим за висотою, якщо для кожної вершини висота її лівого та правого піддерева відрізняється не більше ніж на 1.

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

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

class Tree
{
public:
  TreeNode *head;
  Tree() : head(NULL) {};
  void Insert(int val); // Вставка числа val в Бінарне Дерево Пошуку
  int IsBalanced(void); // Повернути 1 якщо дерево збалансоване за висотою і 0 в іншому випадку
};

// Java
class TreeNode
{
  int val;
  TreeNode left, right;
  TreeNode(int x)
  {
    val = x;
    left = right = null;
  }
}

class Tree
{
  TreeNode head;
  Tree();
  void Insert(int val); // Вставка числа val в Бінарне Дерево Пошуку
  int IsBalanced(); // Повернути 1 якщо дерево збалансоване за висотою і 0 в іншому випадку
}

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

Вхідні дані

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

Вихідні дані

Побудуйте Бінарне Дерево Пошуку з вхідних даних. Виведіть 1, якщо воно збалансоване за висотою, і 0 в іншому випадку.

Приклади