Ich wurde in einem Interview gebeten, einen ausgeglichenen binären Suchbaum aus einem sortierten Array mit Rekursion und ohne Rekursion zu konstruieren. Ich war in der Lage, mit Rekursion eine Lösung zu finden, konnte aber keine Lösung ohne Rekursion finden. Kann jemand eine Lösung für dieses Problem ohne Rekursion bereitstellen?Sortiertes Array zu Balanced Binary Search Tree ohne Rekursion
Sie können einen eigenen Stapel erstellen und verwenden (z. B. als Array oder verknüpfte Liste) und auf ihn innerhalb einer Schleife zugreifen.
Jede Zelle im Array oder in der Liste muss die wesentlichen Informationen über Ihren Baum speichern, die sonst von den rekursiven Funktionen verwaltet würden.
Einige Informationen aus Ihrer rekursiven Version (z. B. ein Tiefenzähler) können möglicherweise von lokalen Variablen verarbeitet werden. Für einige Probleme können Sie möglicherweise alle solche Informationen aus Ihrem Stapel in lokale Variablen verschieben; In solchen Fällen benötigen Sie keinen expliziten Stack.
Geben Sie an, mit welcher Sprache Sie arbeiten, und fügen Sie ein Tag für diese Sprache hinzu. –
Rekursionen können immer mit Hilfe eines Stacks in eine Schleife umgewandelt werden. – HenryLee
@AndrewMyers diese Frage ist eine schlechte Passform für Programmierer - es würde schnell abgelehnt werden und geschlossen dort, siehe [Warum Interview Fragen machen schlechte Programmers.SE Fragen?] (Http://meta.programmers.stackexchange.com/ a/6361/31260) Empfohlene Lektüre: ** [Was geht auf Programmers.SE? Ein Leitfaden für Stack Overflow] (http://meta.programmers.stackexchange.com/q/7182/31260) ** – gnat