1 до n по очереди вставляют в изначально пустое двоичное дерево поиска в порядке, заданном массивом keys. Первое число становится корнем, каждое следующее спускается от корня — влево, если оно меньше текущей вершины, вправо, если больше, — и становится новым листом там, где места нет.
Верните высоту получившегося дерева — число вершин на самом длинном пути от корня до листа.
Простое моделирование вставок может работать за O(n²), если дерево выродится в цепочку. Попробуйте быстрее.keys=[3, 1, 2, 5, 4] → 3
Корень 3; 1 уходит влево, 2 — правый ребёнок 1; 5 — правый ребёнок 3, 4 — левый ребёнок 5. Самые длинные пути 3 → 1 → 2 и 3 → 5 → 4 содержат по 3 вершины.
keys=[1, 2, 3] → 3
Ключи идут по возрастанию, и дерево вытягивается в цепочку вправо высотой 3.
keys=[4, 2, 6, 1, 3, 5, 7] → 3
Получается идеально сбалансированное дерево из трёх уровней.
keys — перестановка чисел от 1 до nkeys=[3, 1, 2, 5, 4]
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 109 тестов на сервере, включая скрытые.