Encontre o número de nós que têm apenas um único filho
A construção de uma árvore binária pode ser feita de forma recursiva. Suponhamos que a árvore seja construída com base na entrada do utilizador. Se o nó não existir, o utilizador insere 0 e, se existir, insere um número positivo.
Partindo da raiz, podemos ler a entrada do utilizador e avançar na direção de uma subárvore se o número for positivo, interrompendo a recursão nesse ponto caso seja 0.
vals = map(int, input().split()) # Lê os valores da BST a partir da entrada
idx = 0 # Índice atual de valor
root = Node(vals[idx]) # Define o valor do nó raiz
def read(node: Node): # Lê recursivamente todos os dados da árvore
if node.value == 0: # Se o valor atual for 0 => o nó não existe
return # Então não lemos seus filhos à esquerda e à direita
node.left = Node(vals[idx + 1]) # Define o valor do nó esquerdo
node.right = Node(vals[idx + 2]) # Define o valor do nó direito
idx += 2 # Atualiza o índice atual de valor
read(node.left) # Pede dados ao utilizador para a subárvore esquerda
read(node.right) # Pede dados ao utilizador para a subárvore direitaAqui, pode-se observar que o número de nós não é determinado inicialmente. O programa lê recursivamente todas as entradas começando pelo nó à esquerda, propagando-se até que o valor do nó seja 0. Em seguida, continua lendo os valores para o nó à direita. Esse processo prossegue até que todos os nós inferiores sejam definidos como 0 e já não haja mais entradas para ler. Assim, para a árvore ilustrada acima, a entrada do utilizador pode ser a seguinte:
1 # raiz
2 # raiz.esquerda
3 # raiz.direita
4 # raiz.esquerda.esquerda
5 # raiz.esquerda.direita
0 # raiz.esquerda.esquerda.esquerda não existe (sem filho esquerdo de 4)
0 # raiz.esquerda.esquerda.direita não existe (sem filho direito de 4)
0 # raiz.esquerda.direita.esquerda não existe (sem filho esquerdo de 5)
0 # raiz.esquerda.direita.direita não existe (sem filho direito de 5)
6 # raiz.direita.esquerda
7 # raiz.direita.direita
0 # raiz.direita.esquerda.esquerda não existe (sem filho esquerdo de 6)
0 # raiz.direita.esquerda.direita não existe (sem filho direito de 6)
8 # raiz.direita.direita.esquerda
9 # raiz.direita.direita.direita
0 # raiz.direita.direita.esquerda.esquerda não existe (sem filho esquerdo de 8)
0 # raiz.direita.direita.esquerda.direita não existe (sem filho direito de 8)
0 # raiz.direita.direita.direita.esquerda não existe (sem filho esquerdo de 9)
0 # raiz.direita.direita.direita.direita não existe (sem filho direito de 9)Esta entrada também pode ser representada como um array -
[1, 2, 3, 4, 5, 0, 0, 0, 0, 6, 7, 0, 0, 8, 9, 0, 0, 0, 0], que corresponderia à árvore binária. Em vez de solicitar que o utilizador introduza um novo número a cada vez, podemos iterar sobre o array e construir a árvore binária de forma recursiva, do mesmo modo que fizemos acima.Dado uma árvore binária válida, o objetivo é calcular quantos nós têm apenas um único filho.
Entrada
A entrada contém inteiros separados por espaços que representam os valores nos nós da árvore binária. A ordem dos valores é dada conforme descrito acima. Um valor de 0 significa que o nó não existe.
Saída
O programa deve imprimir o número de nós em uma árvore binária que têm apenas um filho.
Exemplos
Entrada | Saída |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 0 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 1 |
Explicação
- No primeiro exemplo, a árvore binária não possui nós com apenas um filho
- No segundo exemplo, a árvore binária tem apenas um nó com um filho único: o nó com o número 3.
Pro tip 😎
Pode modificar o código acima para criar nós de forma condicional - crie um nó e atribua-o a
node.left ou node.right somente se o valor inserido for diferente de 0.Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB