pattern heroPT–23LeetCode Extension

Поиск в глубину (DFS)

Идём по одному пути как можно глубже, а в тупике возвращаемся к последней развилке. Так за один обход посещаем всё, что связано со стартом, и ни в одно место не заходим дважды.

Вариант
P14 Поиск в глубину (DFS)Узлы дерева · 1×

Пример задачи: найти глубину двоичного дерева. Каждый узел — объект с полями val, left и right; отсутствующий потомок — none.

nonenonenonenonenonenone84121014стек вызововвершина справа8
ещё не посещёнждёт в стеке вызововтекущий вызоввернул глубину, она рядомnone: пустой потомок

8 — узел, а не none: идём дальше

node = 8left = –right = –
01/42
сначала · назад · пуск · шаг
Скорость
1function maxDepth(node):
2 if node is none:
3 return 0
4 left = maxDepth(node.left)
5 right = maxDepth(node.right)
6 return max(left, right) + 1

← → шаг · пробел — пауза

Как узнать

области или острова в сетке, всё, что достижимо из старта, все пути или задача на дереве, которая решается от листьев вверх.

Как решать такие задачи

  1. Спроси, что узлу нужно от потомков, чтобы получить свой ответ: глубина, сумма, да или нет.
  2. Напиши f(node). Если node — none, верни ответ для пустого дерева.
  3. Вызови f(node.left) и f(node.right) и объедини два ответа со своим val.
  4. Если информация идёт сверху вниз (накопленная сумма, путь до узла), передавай её аргументом.

Вариант: Сверху вниз

То же, но сведения передаём сверху вниз: узел получает от родителя то, что известно о пути от корня, и передаёт детям дальше. Так удобно, когда вопрос про путь от корня, а не про поддерево.

  1. Спроси, что узлу нужно знать о пути над ним: сумму на данный момент, число, собранное из цифр, допустимый диапазон.
  2. Передавай это аргументом обоим потомкам, учтя свой val.
  3. Решай в листьях, а ответ отправляй вверх: true, если хоть один потомок сказал true. Можно вернуться сразу, как только он скажет.
  4. В задаче про сумму чисел от корня до листьев вниз передают number × 10 + val, а числа в листьях складывают.
  5. Чтобы проверить дерево поиска, передавай вниз границы: левый потомок получает (low, node.val), правый — (node.val, high), и каждый val должен в них попадать.

Вариант: Граф

То же, но в графе к одной вершине могут вести разные пути и бывают циклы. Поэтому посещённые вершины отмечаем, чтобы не зайти в них снова.

  1. Определи, что здесь вершина (узел, клетка, состояние) и кто её соседи.
  2. Напиши dfs(вершина): сначала добавь её в visited, потом вызови dfs для каждого соседа, которого там ещё нет.
  3. Запускай dfs из каждой вершины, которую ещё никто не посетил. Каждый такой запуск — новая компонента связности.
  4. Чтобы что-то посчитать, возвращай это из dfs и собирай ответы вызовов ниже: размер, путь, нашлась ли цель.

Вариант: Сетка

То же, но на сетке: клетки — это вершины, а соседние клетки связаны. Обход из клетки находит всю её область, например весь остров.

  1. Определи, что здесь вершина (клетка, узел, состояние) и кто её соседи.
  2. Напиши dfs(вершина): сначала отметь её посещённой, потом вызови dfs для каждого непосещённого соседа.
  3. Запускай dfs из каждой вершины, которую ещё никто не посетил. Каждый такой запуск — новая область.
  4. Чтобы что-то посчитать, возвращай это из dfs и собирай ответы вызовов ниже: размер, глубину, путь.

Где встречается

  • Обход папок. find и du заходят в папку, потом в её первую подпапку, и так до дна, а потом возвращаются. du складывает размер папки из размеров подпапок: ответ дерева из ответов поддеревьев.
  • Сборка мусора. Сборщик мусора в Java начинает с переменных программы и идёт по ссылкам вглубь, отмечая всё живое. Всё, до чего он не дошёл, — мусор.
  • Заливка. Инструмент «Заливка» в графическом редакторе закрашивает пиксель и идёт к соседям того же цвета, пока область не кончится. Классическая версия — обход области в глубину.