Leetcode - 105. Binärbaum aus Vorordnung und Inordnungstraversierung konstruieren

Der Text diskutiert zwei Methoden zum Erstellen eines binären Baums aus seinen Preorder- und Inorder-Durchläufen. Die erste, eine naive rekursive Herangehensweise, verwendet `slice()` und `indexOf()`, was zu einer Zeitkomplexität von O(n²) führt. Diese einfache Methode identifiziert die Wurzel, findet ihre Position im Inorder-Array und konstruiert rekursiv die linken und rechten Teilbäume. Die wiederholte Array-Slicing verursacht zusätzliche Overhead-Kosten in der naiven Methode. Die naive Herangehensweise hat eine Raumkomplexität von O(n) aufgrund von Rekursion und geschnittenen Arrays. Die zweite Herangehensweise ist optimiert und nutzt eine Hash-Karte und Index-Zeiger für Effizienz. Diese optimierte Methode verwendet eine Hash-Karte für konstante Zeit-Lookups von Knoten-Indizes im Inorder-Durchlauf. Index-Zeiger ersetzen das Slicing und vermeiden unnötiges Array-Kopieren in der optimierten Methode. Die optimierte Herangehensweise erreicht eine Zeitkomplexität von O(n), indem sie wiederholte Array-Operationen vermeidet. Die Raumkomplexität bleibt bei O(n) für die Hash-Karte und Rekursion in der optimierten Version. Die optimierte Herangehensweise ist erheblich schneller als die naive Implementierung. Zusammenfassend bietet die Verwendung einer Hash-Karte und Index-Zeiger signifikante Leistungsvorteile.