Escreva a função que retorna o número de nós que são divisores da soma de seus filhos. Leve em conta apenas os nós com dois filhos.
Passo 1
A questão pede para escrever uma função que, dado uma árvore binária, conte quantos nós que possuem exatamente dois filhos têm o seu próprio valor como divisor da soma dos valores desses dois filhos. O tópico aqui é percorrer árvores binárias usando recursão e aplicar a definição de divisor (resto zero na divisão inteira).
Passo 2
Para resolver, vamos usar uma travessia recursiva (por exemplo, pós-ordem) que em cada chamada retorna a quantidade de nós válidos na subárvore. Em cada nó, primeiro processamos as subárvores dos filhos para obter suas contagens, e depois avaliamos o próprio nó.
Passo 3
No passo de avaliação do nó atual, verificamos se ele possui os dois filhos não nulos. Se não possuir, contribuímos com zero para o total. Se o nó tem ambos os filhos, calculamos a soma dos valores dos filhos e checamos se essa soma é divisível pelo valor do nó, ou seja, se
. Se for, somamos 1; caso contrário, 0.
Passo 4
A função final faz a chamada recursiva para a raiz e retorna o total de nós válidos obtido da subárvore inteira.
Resposta
def conta_nos_divisores(raiz):
# Função auxiliar que retorna (contagem, _) onde _ é irrelevante aqui
def percorre(no):
if no is None:
return 0
# conta nos da subárvore esquerda e direita
cont_esq = percorre(no.esquerda)
cont_dir = percorre(no.direita)
cont_atual = 0
# checa se tem exatamente dois filhos
if no.esquerda is not None and no.direita is not None:
soma_filhos = no.esquerda.valor + no.direita.valor
# verifica se o valor do nó divide a soma dos filhos
if soma_filhos % no.valor == 0:
cont_atual = 1
return cont_esq + cont_dir + cont_atual
return percorre(raiz)
# Função auxiliar que retorna (contagem, _) onde _ é irrelevante aqui
def percorre(no):
if no is None:
return 0
# conta nos da subárvore esquerda e direita
cont_esq = percorre(no.esquerda)
cont_dir = percorre(no.direita)
cont_atual = 0
# checa se tem exatamente dois filhos
if no.esquerda is not None and no.direita is not None:
soma_filhos = no.esquerda.valor + no.direita.valor
# verifica se o valor do nó divide a soma dos filhos
if soma_filhos % no.valor == 0:
cont_atual = 1
return cont_esq + cont_dir + cont_atual
return percorre(raiz)