Ist der Binärbaum vollständig?
Sie sollen überprüfen, ob der vorliegende Binärbaum vollständig ist.
Ein Binärbaum gilt als vollständig, wenn alle Ebenen des Baumes vollständig besetzt sind und nur die unterste Ebene von links her aufgefüllt ist, soweit Knoten vorhanden sind.
Beide der unten dargestellten Bäume sind vollständige Binärbäume.
Eingabe
Die Eingabe enthält durch Leerzeichen getrennte ganze Zahlen, die die Werte in den Knoten des Binärbaumes repräsentieren. Die Reihenfolge der Werte wird wie in der vorherigen Erklärung beschrieben angegeben (indem man jeweils von links zum rechten Teilbaum weitergeht). Ein Wert von 0 bedeutet, dass der entsprechende Knoten nicht existiert. Es ist garantiert, dass der übergebene Binärbaum gültig ist.
Ausgabe
Das Programm soll im Fall eines vollständigen Binärbaumes "Yes" ausgeben und andernfalls "No".
Beispiele
Eingabe | Ausgabe |
|---|---|
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 |
Erklärung
Beispiel 1 ist ein vollständiger Binärbaum, da die letzte Ebene von links her aufgefüllt ist
Beispiel 2 ist ebenfalls ein vollständiger Binärbaum, da die letzte Ebene von links her aufgefüllt ist
Beispiel 3 ist kein vollständiger Binärbaum, da er nicht von ganz links ausgefüllt ist
Beispiel 4 ist kein vollständiger Binärbaum, da er nicht von ganz links ausgefüllt ist
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB