Выбор ответа Middle Деревья обновлено
Проверка сбалансированности
Вопрос
Проверяем, что дерево сбалансировано (высоты поддеревьев любого узла отличаются не больше чем на 1). Наивно для каждого узла считаем высоты заново. Как получить O(n)?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Post-order: возвращать высоту или -1 при дисбалансе. Высота считается снизу вверх один раз на узел, и сразу проверяется условие.
Варианты ответа
- Post-order: возвращать высоту или
-1при дисбалансеправильный ответ - Это невозможно: высоты всё равно считаются для каждого узла
- BFS по уровням и проверка, что уровни заполнены
- Сравнить минимальную и максимальную глубину листьев
Разбор
Высота считается снизу вверх один раз на узел, и сразу проверяется условие. Наивный вариант O(n log n) для сбалансированных и O(n²) для вырожденных деревьев.
- O(n) возможно, как описано.
- BFS не даёт высот поддеревьев.
- Разница глубин листьев не равна определению: можно построить сбалансированное по определению дерево, где листья различаются по глубине больше чем на 1.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.