0Pricing
DSA Interview Prep · Aula

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 DSA 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 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.

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 4

BFS 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))  # 3

Visã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))  # 2

Conectando 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 DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA 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 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 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 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

  1. Classe TreeNode e BFS por Níveis
  2. DFS em Ordem, Pré-Ordem e Pós-Ordem
  3. Diâmetro, Altura e Árvores Balanceadas
  4. Soma de Caminhos e Ancestral Comum Mais Baixo
← Voltar para DSA Interview Prep