Trova il numero di nodi con un solo figlio
La costruzione di un albero binario può essere effettuata in modo ricorsivo. Supponiamo di costruire l’albero in base a dati forniti dall’utente. Se un nodo non esiste, l’utente inserisce 0; se invece esiste, viene fornito un numero positivo.
A partire dal nodo radice, si legge il valore fornito dall’utente e, se è positivo, si procede verso il sottoalbero corrispondente; se il valore è 0, si interrompe la costruzione di quel ramo.
vals = map(int, input().split()) # Legge i valori del BST dall'input
idx = 0 # Indice del valore corrente
root = Node(vals[idx]) # Imposta il valore del nodo radice
def read(node: Node): # Legge ricorsivamente tutti i dati nell'albero
if node.value == 0: # Se il valore corrente è 0 => il nodo non esiste
return # Quindi non si leggono i figli sinistro e destro
node.left = Node(vals[idx + 1]) # Imposta il valore del nodo sinistro
node.right = Node(vals[idx + 2]) # Imposta il valore del nodo destro
idx += 2 # Aggiorna l'indice del valore corrente
read(node.left) # Legge i dati dal sottoalbero sinistro
read(node.right) # Legge i dati dal sottoalbero destroQui si può notare che il numero di nodi non è determinato inizialmente. Il programma legge ricorsivamente tutti i valori, partendo dal nodo sinistro e procedendo fino a quando il valore del nodo è 0. A quel punto si passa a leggere i valori per il ramo destro. Questo processo termina quando tutti i nodi in fondo hanno valore 0 e non ci sono più dati da leggere. Nell’esempio della figura, l’input dell’utente potrebbe essere:
1 # root
2 # root.left
3 # root.right
4 # root.left.left
5 # root.left.right
0 # root.left.left.left does not exist (no left child of 4)
0 # root.left.left.right does not exist (no right child of 4)
0 # root.left.right.left does not exist (no left child of 5)
0 # root.left.right.right does not exist (no right child of 5)
6 # root.right.left
7 # root.right.right
0 # root.right.left.left does not exist (no left child of 6)
0 # root.right.left.right does not exist (no right child of 6)
8 # root.right.right.left
9 # root.right.right.right
0 # root.right.right.left.left does not exist (no left child of 8)
0 # root.right.right.left.right does not exist (no right child of 8)
0 # root.right.right.right.left does not exist (no left child of 9)
0 # root.right.right.right.right does not exist (no right child of 9)Questo input può anche essere rappresentato come array:
[1, 2, 3, 4, 5, 0, 0, 0, 0, 6, 7, 0, 0, 8, 9, 0, 0, 0, 0], che corrisponde allo stesso albero binario. Invece di richiedere ogni volta un nuovo numero all’utente, si potrebbe semplicemente iterare sull’array e costruire ricorsivamente l’albero allo stesso modo.Dato un albero binario valido, viene richiesto di calcolare il numero di nodi che hanno un solo figlio.
Input
L’input contiene numeri interi separati da spazi che rappresentano i valori dei nodi di un albero binario, nell’ordine descritto in precedenza. Un valore pari a 0 significa che il nodo non esiste.
Output
Il programma deve stampare il numero di nodi in un albero binario che hanno un solo figlio.
Examples
Input | Output |
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 |
Spiegazione
- Nel primo esempio, l’albero binario non presenta nodi con un singolo figlio
- Nel secondo esempio, l’albero binario ha un solo nodo con un figlio soltanto: il nodo con il valore 3.
Pro tip 😎
È possibile modificare il codice precedente per creare i nodi in maniera condizionale: si istanzia un nuovo nodo e lo si assegna a
node.left o node.right solo se il valore letto in input è diverso da 0.Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB