Объясни рекурсию на деревьях
Вопрос
Объясни, как ты решаешь задачи на деревья рекурсией, на примере проверки, что дерево является BST. Какая сложность?
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Формулирует, что функция возвращает для поддерева
Называет базовый случай: пустой узел
Передаёт границы lo и hi сверху вниз
Объясняет, почему сравнения только с детьми недостаточно
O(n) времени и O(h) памяти на стек
Что могут спросить следом
- Как сделать это итеративно?
- Как проверить через in-order обход?
- Что если в дереве дубликаты?
Разбор
Сначала решаю, что функция возвращает для поддерева и какие параметры ей нужны. Для проверки BST мало сравнить узел с детьми: значение глубоко в левом поддереве тоже обязано быть меньше корня. Поэтому функция принимает узел и допустимый интервал (lo, hi). Базовый случай: пустой узел валиден. Если значение вне интервала, возвращаю false. Иначе проверяю левое поддерево с интервалом (lo, node.val) и правое с (node.val, hi). Каждый узел посещается один раз: O(n) времени, память O(h) на стек, для вырожденного дерева O(n). Альтернатива: in-order обход и проверка, что значения строго возрастают; его легко сделать итеративно через стек.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.