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)
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)