Faça uma função que retorne a quantidade de folhas de uma árvore binária de busca.

Passo 1

O problema pede uma função que receba a raiz de uma árvore binária de busca e retorne quantos nós folha ela tem. Vamos usar o conceito de BST apenas para ilustrar o tipo de árvore, mas o algoritmo de contagem de folhas vale para qualquer árvore binária.

Passo 2

Uma folha é um nó que não tem filhos: ou seja, seus ponteiros para a subárvore esquerda e direita são nulos. Precisamos reconhecer esse caso para contar +1.

Passo 3

Para percorrer todos os nós e detectar as folhas, a técnica mais simples é a recursão. A ideia é: para cada nó, contamos as folhas da subárvore esquerda, contamos as folhas da subárvore direita e somamos. Mas se o nó for folha contamos 1, e se for nulo contamos 0.

Passo 4

Em detalhes, para cada chamada recursiva com um nó genérico:
  • Se o nó for None, não há folha: retornar 0.
  • Se o nó tiver ambos os filhos None, é folha: retornar 1.
  • Caso contrário, retornar a soma das contagens das chamadas recursivas na esquerda e na direita.
    Agora que temos o raciocínio claro, basta transformar essa lógica em código. A seguir, a implementação em Python, assumindo que cada nó tenha os atributos ‘esquerda’ e ‘direita’.

Resposta

def contar_folhas(raiz):
if raiz is None:
return 0
# se não há filhos, é folha
if raiz.esquerda is None and raiz.direita is None:
return 1
# soma as folhas das subárvores esquerda e direita
return contar_folhas(raiz.esquerda) + contar_folhas(raiz.direita)

Exercícios relacionados