Finde die Anzahl von Knoten, die genau ein Kind haben
Das Erstellen eines Binärbaums kann rekursiv erfolgen. Wir gehen davon aus, dass der Baum auf Grundlage der Benutzereingaben aufgebaut wird. Wenn ein Knoten nicht existiert, gibt der Benutzer 0 ein; wenn er existiert, besitzt er eine positive Zahl.
Ausgehend von der Wurzel lesen wir die Benutzereingabe und gehen in Richtung eines Teilbaums weiter, falls die Zahl positiv war, während wir den rekursiven Aufbau beenden, wenn die Zahl 0 ist.
vals = map(int, input().split()) # Liest die Werte des BST aus der Eingabe
idx = 0 # Der aktuelle Wertindex
root = Node(vals[idx]) # Setzt den Wert des Wurzelknotens
def read(node: Node): # Liest rekursiv alle Daten des Baums
if node.value == 0: # Wenn der aktuelle Wert 0 ist => Knoten existiert nicht
return # Wir lesen also nicht weiter seine linken und rechten Kinder
node.left = Node(vals[idx + 1]) # Legt den Wert des linken Knotens fest
node.right = Node(vals[idx + 2]) # Legt den Wert des rechten Knotens fest
idx += 2 # Aktualisiert den aktuellen Wertindex
read(node.left) # Liest die Daten des linken Teilbaums
read(node.right) # Liest die Daten des rechten TeilbaumsHier kannst du erkennen, dass die Anzahl der Knoten am Anfang nicht festgelegt ist. Das Programm liest alle Eingaben rekursiv ein, beginnend vom linken Teilbaum bis zu dem Punkt, an dem der Knotenwert 0 ist. Anschließend werden die Werte für den rechten Teilbaum eingelesen. Dieser Prozess läuft weiter, bis alle Blätterknoten 0 sind und keine weiteren Eingaben mehr vorhanden sind. Für den oben abgebildeten Baum könnte die Benutzereingabe beispielsweise so aussehen:
1 # root
2 # root.left
3 # root.right
4 # root.left.left
5 # root.left.right
0 # root.left.left.left existiert nicht (kein linkes Kind von 4)
0 # root.left.left.right existiert nicht (kein rechtes Kind von 4)
0 # root.left.right.left existiert nicht (kein linkes Kind von 5)
0 # root.left.right.right existiert nicht (kein rechtes Kind von 5)
6 # root.right.left
7 # root.right.right
0 # root.right.left.left existiert nicht (kein linkes Kind von 6)
0 # root.right.left.right existiert nicht (kein rechtes Kind von 6)
8 # root.right.right.left
9 # root.right.right.right
0 # root.right.right.left.left existiert nicht (kein linkes Kind von 8)
0 # root.right.right.left.right existiert nicht (kein rechtes Kind von 8)
0 # root.right.right.right.left existiert nicht (kein linkes Kind von 9)
0 # root.right.right.right.right existiert nicht (kein rechtes Kind von 9)Diese Eingabe kann auch als Array dargestellt werden –
[1, 2, 3, 4, 5, 0, 0, 0, 0, 6, 7, 0, 0, 8, 9, 0, 0, 0, 0], was demselben Binärbaum entspricht. Anstelle den Benutzer jedes Mal nach der Eingabe zu fragen, könnten wir auch über das Array iterieren und auf dieselbe Weise rekursiv einen Binärbaum erstellen, wie oben demonstriert.Gegeben ist ein gültiger Binärbaum. Deine Aufgabe besteht darin, die Anzahl der Knoten zu berechnen, die genau ein Kind besitzen.
Eingabe
Die Eingabe enthält durch Leerzeichen getrennte Ganzzahlen, die die Werte in den Knoten des Binärbaums darstellen. Die Reihenfolge der Werte ist so strukturiert, wie oben beschrieben. Eine 0 bedeutet, dass der entsprechende Knoten nicht existiert.
Ausgabe
Das Programm soll die Anzahl der Knoten im Binärbaum ausgeben, die genau ein Kind haben.
Beispiele
Eingabe | Ausgabe |
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 |
Erklärung
- Im ersten Beispiel besitzt der Binärbaum keine Knoten, die nur ein Kind haben.
- Im zweiten Beispiel gibt es genau einen Knoten mit nur einem Kind – den Knoten mit der Zahl 3.
Profi-Tipp 😎
Du kannst den oben gezeigten Code so anpassen, dass Knoten nur dann erstellt werden, wenn der eingelesene Wert ungleich 0 ist – in diesem Fall wird ein neuer Knoten erzeugt und
node.left bzw. node.right zugewiesen.Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB