Алгоритмы с нуля
Деревья: тест на припоминание
Припоминание сильнее перечитывания. Для каждого промпта произнеси или запиши полный ответ по памяти, прежде чем открыть модельный ответ — именно усилие припоминания закрепляет структуру.
Восстанови хребет юнита — почему рекурсия подходит дереву, для чего три порядка DFS, инвариант BST и оговорка про баланс, когда BFS лучше DFS, и паттерн tree DP — не заглядывая назад в уроки.
- 01Почему рекурсия — естественный способ обработки binary tree?
- 02Назови три traversal в глубину и для чего каждый.
- 03Сформулируй инвариант BST и что он даёт.
- 04Почему O(h) не всегда означает O(log n) для BST и каков худший случай?
- 05Когда выбирать level-order (BFS) вместо traversal в глубину и что заставляет его работать?
- 06Опиши паттерн tree DP и почему возвращаемое значение отличается от ответа.
Если ты смог восстановить каждый ответ по памяти, ты держишь хребет юнита: binary tree определено рекурсивно, поэтому рекурсия (реши поддеревья, скомбинируй с узлом) — универсальный шаблон; три порядка DFS различаются лишь тем, когда посещается узел, и in-order читает BST отсортированным; инвариант BST покупает операции O(h), но только баланс держит h около log n; BFS с очередью и снимком размера на каждом уровне — инструмент, когда важна глубина; а tree DP возвращает продлеваемую локальную информацию вверх, накапливая настоящий глобальный ответ сбоку.