"Zwei Knoten vertauscht, korrigieren Sie die BST" scheint ein sehr diskutierter/beliebter Algorithmus zu sein.Warum sollten zwei Knoten einer BST an der falschen Stelle sein?
Was ist das Besondere an diesem Algorithmus "Tauschen Sie zwei fehlerhafte BST-Knoten" im Gegensatz zu einem anderen allgemeineren BST-Reparaturalgorithmus?
Ich könnte falsch liegen, aber ich vermute, dieses Problem ist 100% erfunden und ist einfach eine gute Übung zu beurteilen, ob Sie ein Handle auf binäre Suchbäume, inorder Traversals und allgemeine Baum Rekursion haben. Es erscheint mir äußerst unwahrscheinlich, dass Sie das jemals in der Praxis anwenden würden, da die Elemente einer BST in der Regel fehlerhaft oder logisch fehlerhaft sind.
Die zweite Frage, die Sie gestellt haben - was ist mit einem allgemeineren "reparieren diesen Baum, um es zu einem binären Suchbaum" Problem zu machen? - ist ein guter. Das ist im Wesentlichen gleichbedeutend mit dem Sortieren der Elemente eines Binärbaums und dem anschließenden Verwenden eines Invers-Traversals, um die Elemente an den richtigen Platz zu bringen (verstehst du warum?). Wieder würde ich sehr überrascht sein, wenn du jemals so etwas getan hättest , da es ungewöhnlich ist, ungeordnete Elemente in einem Binärbaum zu speichern und dann zu entscheiden, sie auf diese Weise neu zu ordnen.
Ahh, also behalten Sie den vorhandenen Baum und überschreiben nur die Knoten, indem Sie eine In-Order-Traversierung durchführen, da die Elemente bereits im Array geordnet sind. Ich dachte nach, wie würdest du einen Baum, den du noch nicht gebaut hast, durchqueren, aber das macht Sinn, dass wir den Baum überschreiben würden. Danke für die Hilfe! –