eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Минимальная глубина Бинарного Дерева

Минимальная глубина Бинарного Дерева

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Задан массив целых чисел. Создайте из них Бинарное Дерево Поиска. Если вставляемое значение равно текущей вершине, то его следует вставлять в правое поддерево.

Реализуйте метод MinDepth, который находит минимальную глубину дерева. Минимальной глубиной называется количество вершин в самом коротком пути от корня до самого ближнего листа.

prb7464.gif

Напишите код согласно следующего интерфейса:

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 в Бинарное Дерево Поиска

int MinDepth(void); // Вернуть минимальную глубину Бинарного Дерева Поиска

};

Вы можете создавать (использовать) по необходимости дополнительные методы.

prb7464.gif

Входные данные

Первая строка содержит число n (1n100). Вторая строка содержит n целых чисел.

Выходные данные

Создайте Бинарное Дерево Поиска из входных данных. Найдите и выведите его минимальную глубину.

Пример

Входные данные #1
4
14 14 9 1
Выходные данные #1
2
Автор Михаил Медведев
Источник Язык С++