Где применяется
1. Задача
Ещё на шаге 68 было предупреждение. Вставь в обычный BST числа 1, 2, 3, 4, 5 по порядку, и каждое новое значение уйдёт вправо. Дерево вытянется в цепочку высотой n, и поиск замедлится с O(log n) до O(n). Это не редкая случайность. Данные часто приходят уже отсортированными или почти отсортированными: временные метки, ID, которые база выдаёт по возрастанию, имена по алфавиту. Поэтому прежде чем чинить перекошенное дерево, надо измерить, насколько оно перекошено. И надо поймать случай, когда наверху всё выглядит ровно, а перекос сидит ниже.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где нужно проверить, сбалансировано ли дерево, или построить сбалансированное. Считай высоты снизу вверх за один проход, а из отсортированных данных строй, ставя середину в корень.
isBalanced из урока, помощник возвращает высоту или сигнал, что дерево уже разбалансировано.
Средний элемент становится корнем, а каждая половина строит поддерево, поэтому высоты отличаются не больше чем на 1.
То же построение из связного списка, середину находишь медленным и быстрым указателями.