В этом посте будет рассмотрена довольно простая задача AlgoExpert — «Поиск в глубину».
В этом посте будет рассмотрена довольно простая задача AlgoExpert — «Поиск в глубину».
На первый взгляд я принял это за BST-задачу поиска в глубину, но, к счастью, перед тем, как начать, я заметил, что это обход дерева.
Деревья интересны мне тем, что они не так просты, как бинарные деревья, и все же почему-то они кажутся более интуитивно понятными в работе. Хотя это может быть потому, что я обычно использую рекурсию в бинарных деревьях и итерацию в деревьях.
Что-то, что помогает мне вспомнить, как подойти к обходу дерева или графа, заключается в том, что поиск в глубину обычно использует стек, а поиск в ширину использует очереди.
Подумав
Так почему именно стек помогает мне пройти через это?
Давайте рассмотрим это шаг за шагом.
Я начинаю с корня («А»), поэтому добавлю его дочерние элементы в стек.
Теперь я перейду к следующему узлу, вытащив его из стека.
А теперь добавьте его дочерние элементы в стек.
Теперь я зайду и в «Е», и в «F» — их тоже лопну.
Отсюда достаточно легко увидеть, чем это заканчивается и почему стек так хорошо подходит для поиска в глубину. Процесс LIFO (последний пришел, первый ушел) естественным образом отдает приоритет глубине.
Реализация:
В AlgoExpert нам будет предоставлен класс Node для реализации метода DFS.
Вместо того, чтобы разбивать этот процесс на части, я просто дам свое полное решение (оно очень простое и понятное).
Массив, который мы возвращаем (как указано в задаче), будет включать все имена узлов в правильном порядке в глубину.
И это все для этого!
Хотя это относительно простая задача, мне все же нравится тратить время на то, чтобы укрепить применение метода. Простые обходы лежат в основе многих других, более сложных задач, и хорошо разбираться в них кажется отличной идеей.
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку. Подпишитесь на нас в Twitter, LinkedIn, и Discord .