Выбор ответа Junior Деревья спрашивают часто обновлено
Сложность максимальной глубины
Вопрос
Какая сложность по времени и памяти у рекурсивного поиска максимальной глубины дерева из n узлов высоты h?
function maxDepth(node) {
if (!node) return 0;
return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n) времени, O(h) памяти. Каждый узел посещается один раз: O(n).
Варианты ответа
- O(log n) времени, O(1) памяти
- O(n) времени, O(h) памятиправильный ответ
- O(n²) времени, O(n) памяти
- O(h) времени, O(n) памяти
Разбор
Каждый узел посещается один раз: O(n). Стек рекурсии равен высоте: O(h), то есть O(log n) для сбалансированного и O(n) для вырожденного дерева-«палки».
- O(log n) времени невозможно: надо увидеть все листья.
- O(n²) нет: повторных обходов нет.
- Время зависит от n, а не от h.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.