Escreva uma função que faça o percurso em nível em uma árvore binária. O percurso em nível (ou em largura) em uma árvore é um percurso que visita, em ordem crescente, todos os nós de um nível antes de continuar a visita no nível seguinte. Uma das formas de implementar é utilizar uma fila (FIFO) para guardar quais serão os próximos nodes a serem visitados.

Passo 1

O enunciado pede para escrever uma função que percorra uma árvore binária em nível (ou largura), visitando todos os nós de cada nível antes de descer ao próximo, usando uma fila FIFO para controlar a ordem de visita.

Passo 2

Precisamos modelar a árvore com um nó que tenha valor e ponteiros para filho esquerdo e direito. Em Python, por exemplo, definimos uma classe Node assim:
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Passo 3

A ideia do percurso em nível é:
  1. Enfileirar a raiz.
  2. Enquanto a fila não estiver vazia:
    • Desenfileirar o próximo nó.
    • Processar (por exemplo, imprimir ou coletar) seu valor.
    • Se o filho esquerdo existir, enfileirá-lo.
    • Se o filho direito existir, enfileirá-lo.
      Isso garante que a gente visite todos os nós de um nível antes de passar para o próximo.

Passo 4

Em pseudocódigo, usando uma fila Q e lista res para armazenar o resultado, fica assim:
função nivel(root):
  se root for nulo, retorne lista vazia
  Q ← fila vazia
  res ← lista vazia
  enfileira Q, root
  enquanto Q não vazia:
    node ← desenfileira Q
    adiciona node.val em res
    se node.left existe: enfileira Q, node.left
    se node.right existe: enfileira Q, node.right
  devolve res
Agora só falta transformar esse pseudocódigo em uma função Python usando collections.deque para a fila. A função retorna a lista de valores na ordem do percurso em largura.

Resposta

from collections import deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def nivel(root):
    """
    Retorna a lista de valores da árvore em percurso em nível (largura).
    """
    if root is None:
        return []

    resultado = []
    fila = deque([root])

    while fila:
        node = fila.popleft()
        resultado.append(node.val)

        if node.left:
            fila.append(node.left)
        if node.right:
            fila.append(node.right)

    return resultado

Exercícios relacionados