DFS: симметричный, прямой и обратный обход
Реализуйте все три обхода DFS рекурсивно и итеративно с явным стеком, объясняя, когда полезен каждый порядок
«DFS: симметричный, прямой и обратный обход» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Три порядка обхода DFS
DFS двоичного дерева посещает узлы в одном из трёх порядков, зависящих от того, когда обрабатывается корень относительно его потомков. Прямой обход: корень → левое поддерево → правое поддерево. Симметричный обход: левое поддерево → корень → правое поддерево. Обратный обход: левое поддерево → правое поддерево → корень. Названия показывают, где находится корень в последовательности. Важно понимать все три порядка, поскольку для разных задач требуются разные варианты обхода.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre: 1 2 4 5 3
# in: 4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')Рекурсивный прямой обход
При прямом обходе текущий узел обрабатывается до его поддеревьев. Это соответствует естественному чтению дерева сверху вниз; такой обход используется для копирования деревьев, сериализации и вычисления значений префиксных выражений. Рекурсивная реализация очень коротка, но создаёт стек вызовов глубины O(h), где h — высота дерева.
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
if result is None:
result = []
if not root:
return result
result.append(root.val) # PROCESS ROOT FIRST
preorder_v2(root.left, result)
preorder_v2(root.right, result)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root)) # [1, 2, 4, 5, 3]Рекурсивный симметричный обход
Симметричный обход посещает левое поддерево, затем корень, а затем правое поддерево. Для двоичного дерева поиска симметричный обход всегда создаёт отсортированную последовательность. Это свойство используется в задачах проверки BST, поиска k-го наименьшего элемента и преобразования BST в отсортированный массив. Это самый важный вид обхода, который необходимо знать для задач с BST.
def inorder(root, result=None):
if result is None:
result = []
if not root:
return result
inorder(root.left, result) # left subtree first
result.append(root.val) # PROCESS ROOT MIDDLE
inorder(root.right, result) # right subtree last
return result
# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
return root
bst = make_bst()
print(inorder(bst)) # [1, 2, 3, 4, 6] - sorted!Рекурсивный обратный обход
Обратный обход обрабатывает обоих потомков до текущего узла. Такой восходящий порядок естественен, когда вычисление значения родителя зависит от результатов его потомков, например при вычислении размеров поддеревьев, удалении дерева или вычислении значения дерева выражений. В большинстве задач о деревьях, где информация передаётся вверх, используется неявная логика обратного обхода.
def postorder(root, result=None):
if result is None:
result = []
if not root:
return result
postorder(root.left, result) # left subtree
postorder(root.right, result) # right subtree
result.append(root.val) # PROCESS ROOT LAST
return result
# Use case: delete a tree (children before parent)
def delete_tree(root):
if not root:
return
delete_tree(root.left)
delete_tree(root.right)
print(f'Deleting node {root.val}') # safe: children gone
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root)) # [4, 2, 3, 1]Итеративный прямой обход со стеком
Чтобы избежать ограничений глубины рекурсии, реализуйте DFS итеративно с помощью явного стека. Для прямого обхода поместите корень в стек, затем на каждой итерации извлеките узел, запишите его и добавьте сначала правого, а затем левого потомка, чтобы левый обрабатывался первым. Это имитирует поведение стека вызовов по принципу LIFO и является основным подходом для глубоких деревьев, где стандартного ограничения Python на глубину рекурсии в 1000 вызовов было бы недостаточно.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process now
if node.right: # push right FIRST
stack.append(node.right)
if node.left: # push left second (popped first)
stack.append(node.left)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Итеративный симметричный обход со стеком
Итеративный симметричный обход немного сложнее. Используйте стек и указатель curr: двигайтесь влево настолько далеко, насколько возможно, помещая в стек каждый узел. Когда двигаться влево больше нельзя, извлеките узел, запишите его, а затем перейдите вправо. Этот шаблон — двигаться влево до пустого значения, извлечь и обработать узел, затем перейти вправо — является базовым итеративным приёмом и встречается в задачах с итераторами BST.
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
# Go as far left as possible
while curr:
stack.append(curr)
curr = curr.left
# Pop and process
curr = stack.pop()
result.append(curr.val)
# Move to right subtree
curr = curr.right
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root)) # [4, 2, 5, 1, 3]Итеративный обратный обход с двумя стеками
У итеративного обратного обхода есть полезный приём: выполните изменённый прямой обход (корень → правое поддерево → левое поддерево) и собирайте результаты в обратном порядке. Поместите корень в стек, извлеките узел и добавьте его в начало результата, затем поместите в стек левого, а потом правого потомка. Разворот преобразует порядок «корень — правое поддерево — левое поддерево» в «левое поддерево — правое поддерево — корень», то есть именно в обратный обход. Другой вариант — использовать указатель prev, чтобы отслеживать последний посещённый узел, работая с одним стеком.
from collections import deque
def postorder_iterative(root):
if not root:
return []
result = deque()
stack = [root]
while stack:
node = stack.pop()
result.appendleft(node.val) # prepend = reverse pre-order
if node.left:
stack.append(node.left) # push left first
if node.right:
stack.append(node.right) # push right second
return list(result)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root)) # [4, 5, 2, 3, 1]Как выбрать подходящий обход
Выбор правильного обхода — важный показатель на техническом собеседовании. Используйте прямой обход, когда нужно обработать родителя до его потомков, например при сериализации дерева или копировании структуры. Используйте симметричный обход для BST, чтобы воспользоваться свойством отсортированного порядка. Используйте обратный обход при вычислении значений, зависящих от обоих потомков, например высоты, диаметра или суммы поддерева. Для задач о кратчайшем пути и группировке по уровням предпочтителен BFS.
# Pattern summary:
# Pre-order -> top-down: parent info flows DOWN to children
# In-order -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS -> shortest path, level grouping, level averages
# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
if not root:
return 0
left = subtree_sum(root.left)
right = subtree_sum(root.right)
return root.val + left + right # uses children FIRST
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root)) # 6Обход Морриса: симметричный обход за O(1) памяти
Обход Морриса выполняет симметричный обход за O(1) памяти, временно изменяя дерево. Для каждого узла с левым поддеревом найдите предшественника в симметричном обходе — самый правый узел левого поддерева — и свяжите его указатель на правого потомка с текущим узлом. После посещения восстановите связь. Этот продвинутый приём часто встречается на технических собеседованиях высокого уровня, когда интервьюер спрашивает: «Можно ли решить задачу с O(1) дополнительной памяти?»
def morris_inorder(root):
result = []
curr = root
while curr:
if not curr.left:
result.append(curr.val)
curr = curr.right
else:
# Find in-order predecessor
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
# Make thread and move left
pred.right = curr
curr = curr.left
else:
# Remove thread, visit, move right
pred.right = None
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root)) # [1, 2, 3, 4, 6]Восстановление дерева по обходам
Имея массивы прямого и симметричного обходов, можно восстановить исходное дерево. Первый элемент массива прямого обхода всегда является корнем. Найдите этот корень в массиве симметричного обхода: всё слева от него относится к левому поддереву, а всё справа — к правому. Рекурсивно примените тот же подход к подмассивам. Временная сложность составляет O(n) при использовании поиска индекса в хеш-таблице.
def build_from_preorder_inorder(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
# left subtree: inorder[0:mid], preorder[1:mid+1]
root.left = build_from_preorder_inorder(
preorder[1:mid+1], inorder[:mid])
# right subtree: inorder[mid+1:], preorder[mid+1:]
root.right = build_from_preorder_inorder(
preorder[mid+1:], inorder[mid+1:])
return root
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val) # 3 9 20Итоги по времени и памяти обходов
Все три варианта обхода DFS имеют временную сложность O(n), поскольку каждый узел посещается ровно один раз. Пространственная сложность составляет O(h), где h — высота дерева: O(log n) для сбалансированных деревьев и O(n) для вырожденных деревьев из-за стека вызовов или явного стека. Итеративные реализации избегают ограничения Python на глубину рекурсии, но имеют ту же асимптотическую сложность по памяти. Обход Морриса уникальным образом достигает O(1) памяти, повторно используя указатели на правых потомков дерева.
# Complexity table:
# Traversal | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order | O(n) | O(h) | O(h)
# In-order | O(n) | O(h) | O(h)
# Post-order | O(n) | O(h) | O(h)
# Morris | O(n) | O(1) | O(1)
# BFS | O(n) | O(w) | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')Быстрая проверка
Проверьте, насколько хорошо Вы усвоили понятия «структуры данных и алгоритмы — подготовка к техническому собеседованию» из этого урока.
Итоги урока
В этом уроке Вы изучили: три порядка обхода DFS — прямой, симметричный и обратный — и случаи применения каждого из них, рекурсивные и итеративные реализации с использованием явного стека, а также технику Morris O(1) space. Далее мы рассмотрим вычисление диаметра, высоты и сбалансированности двоичных деревьев.
Часто задаваемые вопросы
Урок «DFS: симметричный, прямой и обратный обход» бесплатный?
Да — полный текст урока «DFS: симметричный, прямой и обратный обход» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «DFS: симметричный, прямой и обратный обход»?
Реализуйте все три обхода DFS рекурсивно и итеративно с явным стеком, объясняя, когда полезен каждый порядок Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «DFS: симметричный, прямой и обратный обход»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Класс TreeNode и обход BFS по уровням
- DFS: симметричный, прямой и обратный обход
- Диаметр, высота и сбалансированные деревья
- Сумма путей и наименьший общий предок