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 é:
- Enfileirar a raiz.
- 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