DFS em Ordem, Pré-Ordem e Pós-Ordem
Implemente os três percursos DFS recursiva e iterativamente com uma pilha explícita, explicando quando cada ordem é útil.
DFS em Ordem, Pré-Ordem e Pós-Ordem é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Três ordens de percurso DFS
O DFS em uma árvore binária visita os nós em uma de três ordens, com base no momento em que a raiz é processada em relação aos filhos. Pré-ordem: raiz → esquerda → direita. Em ordem: esquerda → raiz → direita. Pós-ordem: esquerda → direita → raiz. Os nomes indicam onde a raiz fica na sequência. Entender as três ordens é essencial, pois problemas diferentes exigem ordens diferentes.
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')Percurso recursivo em pré-ordem
Na pré-ordem, o nó atual é processado antes de suas subárvores. Isso corresponde à leitura natural de cima para baixo de uma árvore e é usado para copiar árvores, serializar estruturas e avaliar expressões em notação prefixa. A implementação recursiva é muito curta, mas constrói uma pilha de chamadas com profundidade O(h), em que h é a altura da árvore.
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]Percurso recursivo em ordem
O percurso em ordem visita a subárvore esquerda, depois a raiz e, por fim, a subárvore direita. Em uma árvore de busca binária, o percurso em ordem sempre produz uma sequência ordenada — essa propriedade é usada em problemas como validação de BST, k-ésimo menor elemento e conversão de BST em vetor ordenado. É o percurso mais importante para conhecer ao resolver problemas de 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!Percurso recursivo em pós-ordem
O percurso em pós-ordem processa ambos os filhos antes do nó atual. Essa ordem de baixo para cima é natural quando o cálculo do pai depende dos resultados dos filhos — por exemplo, ao calcular tamanhos de subárvores, excluir uma árvore ou avaliar uma árvore de expressões. A maioria dos problemas de árvores que transmite informações para cima usa uma lógica implícita de pós-ordem.
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]Percurso iterativo em pré-ordem com uma pilha
Para evitar limites de profundidade da recursão, implemente o DFS iterativamente usando uma pilha explícita. Para a pré-ordem: empilhe a raiz; em cada iteração, faça pop de um nó, registre-o e empilhe seu filho direito e depois o filho esquerdo (primeiro o direito, para que o esquerdo seja processado primeiro). Isso imita o comportamento LIFO da pilha de chamadas e é a abordagem padrão para árvores profundas, nas quais o limite de recursão padrão de 1000 do Python causaria uma falha.
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]Percurso iterativo em ordem com uma pilha
O percurso iterativo em ordem é um pouco mais complicado. Use uma pilha e um ponteiro curr: avance para a esquerda o máximo possível, empilhando cada nó. Quando não puder mais avançar para a esquerda, faça pop, registre o nó e avance para a direita. Este padrão — empilhar à esquerda até nulo, fazer pop e processar, depois avançar à direita — é uma técnica iterativa fundamental que aparece em problemas de iteradores de 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]Percurso iterativo em pós-ordem com duas pilhas
O percurso iterativo em pós-ordem tem um truque interessante: execute uma pré-ordem modificada (raiz → direita → esquerda) e colete os resultados na ordem inversa. Empilhe a raiz, faça pop e adicione o nó ao início do resultado; depois, empilhe o filho esquerdo e o direito. A inversão transforma raiz-direita-esquerda em esquerda-direita-raiz — exatamente a pós-ordem. Como alternativa, use um ponteiro prev para acompanhar o último nó visitado com uma única pilha.
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]Quando escolher cada percurso
Escolher o percurso correto é um sinal importante em entrevistas. Use a pré-ordem quando precisar processar um pai antes de seus filhos (serializar a árvore, copiar a estrutura). Use o percurso em ordem para BSTs e aproveite a ordenação dos valores. Use a pós-ordem ao calcular valores que dependem de ambos os filhos (altura, diâmetro, soma da subárvore). O BFS é preferível para problemas de caminho mais curto e agrupamento por níveis.
# 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)) # 6Percurso de Morris: espaço O(1) em ordem
O percurso de Morris obtém espaço O(1) no percurso em ordem ao modificar temporariamente a árvore. Para cada nó com uma subárvore esquerda, encontre o predecessor em ordem (o nó mais à direita da subárvore esquerda) e ligue seu ponteiro direito de volta ao nó atual. Depois de visitá-lo, restaure a ligação. Essa técnica avançada é solicitada em entrevistas de alto nível quando o entrevistador pergunta: 'é possível fazer isso com espaço extra 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]Reconstrução da árvore a partir dos percursos
Dado um vetor de pré-ordem e um vetor em ordem, você pode reconstruir a árvore original. O primeiro elemento da pré-ordem é sempre a raiz. Encontre essa raiz no vetor em ordem — tudo à esquerda dela pertence à subárvore esquerda, e tudo à direita pertence à subárvore direita. Aplique esse processo recursivamente aos subvetores. A complexidade temporal é O(n) com uma consulta de índice em uma tabela de dispersão.
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 20Resumo de tempo e espaço dos percursos
Os três percursos do DFS têm complexidade temporal O(n), pois cada nó é visitado exatamente uma vez. A complexidade espacial é O(h), em que h é a altura da árvore — O(log n) para árvores balanceadas e O(n) para árvores degeneradas, devido à pilha de chamadas ou à pilha explícita. As implementações iterativas evitam o limite de recursão do Python, mas usam o mesmo espaço assintótico. O percurso de Morris obtém exclusivamente espaço O(1) ao reutilizar os ponteiros direitos da árvore.
# 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')Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Resumo da lição
Nesta lição, você aprendeu: as três ordens de percurso do DFS (pré-ordem, em ordem e pós-ordem) e quando escolher cada uma; implementações recursivas e iterativas usando uma pilha explícita; e a técnica de Morris com espaço O(1). A seguir, exploraremos como calcular o diâmetro, a altura e o balanceamento de árvores binárias.
Aprenda Python com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 30
- Aulas
- 120
Perguntas Frequentes
A aula “DFS em Ordem, Pré-Ordem e Pós-Ordem” é grátis?
Sim — o texto completo de “DFS em Ordem, Pré-Ordem e Pós-Ordem” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “DFS em Ordem, Pré-Ordem e Pós-Ordem”?
Implemente os três percursos DFS recursiva e iterativamente com uma pilha explícita, explicando quando cada ordem é útil. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “DFS em Ordem, Pré-Ordem e Pós-Ordem”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Classe TreeNode e BFS por Níveis
- DFS em Ordem, Pré-Ordem e Pós-Ordem
- Diâmetro, Altura e Árvores Balanceadas
- Soma de Caminhos e Ancestral Comum Mais Baixo