L’albero binario è completo?
Vi viene richiesto di verificare se l’albero binario fornito è completo.
Un albero binario si definisce completo se tutti i livelli sono completamente riempiti, a eccezione del livello più basso, i cui nodi sono riempiti procedendo il più possibile da sinistra.
Entrambi gli alberi mostrati di seguito sono alberi binari completi.
Input
L’input contiene interi separati da spazi che rappresentano i valori dei nodi nell’albero binario. L’ordine dei valori è fornito come descritto nella precedente spiegazione (attraversando ogni volta il sottoalbero sinistro e poi quello destro). Un valore pari a 0 indica che il nodo non esiste. È garantito che l’albero binario in ingresso sia valido.
Output
Il programma deve stampare
Yes se l’albero binario è completo, altrimenti No.Esempi
Input | Output |
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | Yes |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | Yes |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | No |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | No |
Spiegazione
- L’Esempio 1 è un albero binario completo poiché l’ultimo livello è riempito da sinistra
- L’Esempio 2 è un albero binario completo poiché l’ultimo livello è riempito da sinistra
- L’Esempio 3 non è un albero binario completo perché non è riempito in modo corretto a partire da sinistra
.png?table=block&id=18a2c681-664d-819f-85b9-ce3af67e16f6&cache=v2)
- L’Esempio 4 non è un albero binario completo perché non è riempito in modo corretto a partire da sinistra
.png?table=block&id=18a2c681-664d-81ce-adca-f0c86ab397ae&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB