Faça uma função que retorne a quantidade de nós de uma árvore binária de busca que possuem apenas um filho.
Passo 1
O enunciado pede uma função que, dada uma árvore binária de busca, retorne quantos nós têm exatamente um filho. Vamos usar conceitos de estrutura de árvores e recursão para percorrê-la e contar esses nós.
Passo 2
Em cada chamada, testamos se o nó atual existe. Se for nulo, retornamos 0, porque não há nenhum nó nessa subárvore (condição de parada).
Para um nó não nulo, verificamos se ele tem exatamente um filho usando a expressão lógica (left != None) XOR (right != None). Em código isso pode ser escrito como (node.left is None) != (node.right is None).
Se o nó atual satisfaz essa condição, contabilizamos 1; caso contrário, contabilizamos 0. Depois, somamos recursivamente os resultados das subárvores esquerda e direita.
Para um nó não nulo, verificamos se ele tem exatamente um filho usando a expressão lógica (left != None) XOR (right != None). Em código isso pode ser escrito como (node.left is None) != (node.right is None).
Se o nó atual satisfaz essa condição, contabilizamos 1; caso contrário, contabilizamos 0. Depois, somamos recursivamente os resultados das subárvores esquerda e direita.
Passo 3
A chamada inicial da função sobre a raiz da árvore vai acumular todas essas contagens e devolver o total de nós que possuem apenas um filho.
Resposta
def count_single_child_nodes(root):
# Se chegamos a um nó nulo, não há nada para contar
if root is None:
return 0
# Contamos 1 se existe exatamente um filho (XOR lógico)
count = 1 if (root.left is None) != (root.right is None) else 0
# Somamos recursivamente as contagens das subárvores esquerda e direita
count += count_single_child_nodes(root.left)
count += count_single_child_nodes(root.right)
return count
# Se chegamos a um nó nulo, não há nada para contar
if root is None:
return 0
# Contamos 1 se existe exatamente um filho (XOR lógico)
count = 1 if (root.left is None) != (root.right is None) else 0
# Somamos recursivamente as contagens das subárvores esquerda e direita
count += count_single_child_nodes(root.left)
count += count_single_child_nodes(root.right)
return count