Escreva uma função que calcula a altura de uma árvore binária.

Passo 1

A questão pede para escrever uma função que calcula a altura de uma árvore binária. O conteúdo aqui é recursão e percorrimento de árvores, e vamos precisar entender a definição de altura e como aplicar recursão nos subproblemas.

Passo 2

Primeiro, definimos o caso base: se a árvore for vazia (ou seja, o nó recebido for None), não há nós para contar e retornamos 0.
No caso geral, chamamos recursivamente a função para a subárvore esquerda e para a subárvore direita, obtendo duas alturas parciais.
A altura da árvore atual é o maior valor entre essas duas alturas parciais acrescido de 1 (que representa o nó raiz atual).
Com isso em mãos, basta escrever a função que testa o caso base e faz essas chamadas recursivas de forma direta.

Resposta

def altura(raiz):
if raiz is None:
return 0
altura_esq = altura(raiz.esquerda)
altura_dir = altura(raiz.direita)
return max(altura_esq, altura_dir) + 1

Exercícios relacionados