ich durch algorithmische Fragen gehen und stolperte über folgende Frage: -Python: - Rückgabe Vorordnungsdurchquerung aus der gegebenen Inorder Traversal
Given an inorder traversal of a binary tree, return preorder traversal
Für zB: -
Inorder - [16, 10, 4, 15, 28] sollte vorbestellen zurückkehren [4, 10, 16, 15, 28].
Ich google es, aber konnte keine Lösung finden. Wie kann ich die Preorder-Traversierung erhalten?
Betrachten Sie die folgenden 2 Bäume, sie haben die gleiche Reihenfolge, aber unterschiedliche Pre-Order-Traversalen. Die von Ihnen zur Verfügung gestellte Ausgabe-Vorbestellungs-Traversierung beginnt mit 4 bedeutet, dass der Knoten 4 die Wurzel des Baums sein muss, aber die von Ihnen bereitgestellte Traversierung in der Reihenfolge garantiert keinen Baum mit Knoten 4 als Wurzel.
Diese scheinen keine Binärbäume zu sein. – Marichyasana
Dann welche Art von Bäumen sind sie @Marichyasana? –
Entschuldigung, ich dachte an einen binären Suchbaum. Für eine BST sind die Schlüssel im linken Teilbaum kleiner als der Schlüssel im übergeordneten Knoten, kurz L
Wenn Sie wissen, dass die Eingabe in "inorder" ist. Konstruiere den Baum und führe dann eine Vorbestellung durch. – user1211
Aber ich werde mehrere binäre Bäume mit gegebenem inorder traversal haben. – PythonEnthusiast
"Im Allgemeinen definiert ein einzelner Baumdurchlauf die Struktur des Baums nicht eindeutig." Siehe http://www.cmi.ac.in/~madhavan/courses/programming06/lecture12-21sep2006.txt –