Паттерны задач на trees и graphs

Задачи на trees и graphs начинаются с modeling. Trees обычно имеют implicit child links и не имеют cycles; graphs часто требуют build adjacency и tracking visited nodes. DFS естественен для components и backtracking; BFS естественен для shortest unweighted distance и level order.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Интервьюеры ожидают описание traversal order, переносимого state и причины termination на cyclic inputs.

Типовые ошибки: Tree solution может сломаться, когда hidden input на самом деле graph с shared nodes. Parent pointers могут вызвать revisiting, если не исключить source traversal.

Чеклист:

• Смоделируйте adjacency.
• Выберите DFS или BFS.
• Явно переносите state.
• Используйте visited для cycles.