Classe TreeNode e BFS por Níveis
Construa árvores binárias a partir de arrays, implemente BFS com um deque para imprimir nível a nível e resolva a profundidade máxima usando BFS.
Classe TreeNode e BFS por Níveis é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 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 Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
A Base da Classe TreeNode
Uma árvore binária é uma estrutura de dados hierárquica em que cada nó tem no máximo dois filhos, chamados de esquerdo e direito. Em Python, modelamos um nó com uma classe simples: class TreeNode: def __init__(self, val=0, left=None, right=None). Todo problema de árvores em entrevistas começa com essa definição — você a verá no código padrão de praticamente todo problema de árvores do LeetCode.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a small tree manually:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)Construindo Árvores a Partir de Vetores
Problemas de entrevistas frequentemente fornecem uma árvore representada como um vetor em ordem de nível, em que None indica nós ausentes. Dado o índice i, o filho esquerdo está em 2i+1 e o filho direito, em 2i+2. Escrever uma função auxiliar para desserializar esse vetor em TreeNodes encadeados é um recurso valioso que economiza tempo durante as sessões de prática.
from collections import deque
def build_tree(arr):
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
q = deque([root])
i = 1
while q and i < len(arr):
node = q.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
q.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
q.append(node.right)
i += 1
return root
root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)O que é BFS e por que uma Fila
A Busca em Largura (BFS) visita todos os nós na profundidade d antes de visitar qualquer nó na profundidade d+1. Esse percurso nível a nível é exatamente o que uma fila (FIFO) nos oferece: enfileiramos a raiz, processamos os nós um de cada vez e enfileiramos os filhos de cada nó à medida que avançamos. O collections.deque do Python oferece appendleft e popleft em O(1), o que faz dele uma escolha adequada em vez de uma lista simples.
from collections import deque
def bfs_print(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root) # 1 2 3 4BFS em Ordem de Nível: Agrupamento por Nível
A variante padrão da BFS agrupa os nós em níveis registrando o tamanho da fila no início de cada iteração. Processe exatamente essa quantidade de nós, reúna seus valores e passe ao nível seguinte. Isso produz uma lista de listas — um formato de saída muito comum em entrevistas para problemas como percurso de árvore binária em ordem de nível, percurso em zigue-zague e visão do lado direito.
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root)) # [[1], [2, 3], [4]]Profundidade Máxima por BFS
A profundidade máxima de uma árvore binária é igual ao número de níveis em seu percurso BFS. Basta contar quantas vezes você conclui o laço de um nível. Isso fornece uma solução com tempo O(n) e espaço O(w), em que w é a largura máxima da árvore. Em uma árvore balanceada, w é O(n/2), portanto o espaço no pior caso é O(n).
from collections import deque
def max_depth_bfs(root):
if not root:
return 0
depth = 0
q = deque([root])
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root)) # 3Visão do Lado Direito de uma Árvore Binária
A visão do lado direito retorna o último nó visível quando você olha para a árvore pela direita — ou seja, o último elemento de cada nível no percurso BFS. Essa é uma aplicação direta da BFS em ordem de nível: reúna o nó final em cada laço de nível. A complexidade temporal é O(n), e o espaço é O(w) para a fila.
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root)) # [1, 3, 5]Percurso em níveis em zigue-zague
No percurso em zigue-zague, os níveis ímpares são coletados da esquerda para a direita, e os níveis pares, da direita para a esquerda. A implementação mais simples mantém a fila do BFS inalterada e simplesmente inverte as listas de níveis alternados antes de adicioná-las ao resultado. Controle a direção com um indicador booleano que muda a cada nível. Isso evita a complexidade de uma fila de duas extremidades no laço interno.
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))Análise da complexidade espacial do BFS
O BFS usa espaço O(w), em que w é a largura máxima da árvore. Em uma árvore binária perfeita com n nós, o último nível tem (n+1)/2 nós — portanto, o BFS pode manter até n/2 nós na fila simultaneamente. Isso faz com que o BFS seja pior em espaço do que o DFS (O(h)) para árvores balanceadas largas, mas melhor para árvores profundas e degeneradas, nas quais a profundidade da pilha de chamadas do DFS é igual a n.
# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)
# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)
from collections import deque
def skewed_tree(n):
root = TreeNode(1)
cur = root
for i in range(2, n+1):
cur.right = TreeNode(i)
cur = cur.right
return root
root = skewed_tree(10)
print('BFS on skewed tree is safe')Média dos níveis em uma árvore binária
Calcular o valor médio em cada nível é outra aplicação direta do BFS. Some todos os valores de um nível, divida pela quantidade de nós e use append para adicioná-lo à lista de resultados. Esse problema verifica se você consegue fazer cálculos aritméticos dentro do laço de níveis. Sempre use a divisão de float no Python 3 (o operador /) e trate o caso-limite da árvore vazia no início.
from collections import deque
def average_of_levels(root):
if not root:
return []
result = []
q = deque([root])
while q:
size = len(q)
total = 0
for _ in range(size):
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(total / size)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root)) # [3.0, 14.5, 11.0]Profundidade mínima usando BFS
A profundidade mínima é a distância da raiz até o nó folha mais próximo (um nó sem filhos). O BFS encontra essa profundidade de forma ideal: o primeiro nó folha encontrado durante o percurso em níveis estará necessariamente na profundidade mínima. Retorne a profundidade atual assim que encontrar uma folha. A complexidade é O(n) no pior caso, mas o percurso costuma terminar muito antes em árvores balanceadas.
from collections import deque
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# A leaf has no children
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0
root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5) # leaf at depth 2
print(min_depth(root)) # 2Conectando irmãos na ordem por níveis
O problema de preencher ponteiros para a direita seguinte pede que você ligue cada nó ao seu vizinho à direita no mesmo nível. Com BFS, isso é simples: dentro do laço de cada nível, defina node.next = q[0] para todos os nós, exceto o último. Este é um exemplo clássico em que o BFS torna a solução evidente, enquanto o DFS exige um controle cuidadoso dos ponteiros entre subárvores.
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
print('BFS connect: O(n) time, O(w) space')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: a definição da classe TreeNode e como construir árvores a partir de vetores; o BFS em níveis usando uma fila de duas extremidades, com a técnica do tamanho do nível para agrupar nós; e aplicações como profundidade máxima, profundidade mínima, visão do lado direito, percurso em zigue-zague e média dos níveis. A seguir, exploraremos as ordens de percurso recursivo do DFS.
Perguntas Frequentes
A aula “Classe TreeNode e BFS por Níveis” é grátis?
Sim — o texto completo de “Classe TreeNode e BFS por Níveis” é 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 Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Classe TreeNode e BFS por Níveis”?
Construa árvores binárias a partir de arrays, implemente BFS com um deque para imprimir nível a nível e resolva a profundidade máxima usando BFS. Você pratica Coding 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 Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding 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 1 de 4.
Quanto tempo leva a aula “Classe TreeNode e BFS por Níveis”?
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 Coding Interview Prep?
Sim. Cada aula de Coding 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