Leetcode - 105. Construire un arbre binaire à partir de parcours préfixe et infixé

Le texte discute de deux méthodes pour construire un arbre binaire à partir de ses parcours préordre et ordre. La première, une approche récursive naïve, utilise `slice()` et `indexOf()`, ce qui entraîne une complexité temporelle de O(n²). Cette méthode simple identifie la racine, trouve sa position dans le tableau d'ordre, et construit récursivement les sous-arbres gauche et droit. Les tranches répétées du tableau entraînent un surcoût supplémentaire dans la méthode naïve. L'approche naïve a une complexité spatiale de O(n) en raison de la récursion et des tableaux tranchés. La deuxième approche est optimisée, utilisant une carte de hachage et des pointeurs d'index pour améliorer l'efficacité. Cette méthode optimisée utilise une carte de hachage pour des recherches d'indices de nœuds en temps constant dans le parcours d'ordre. Les pointeurs d'index remplacent les tranches, évitant les copies inutiles de tableau dans la méthode optimisée. L'approche optimisée atteint une complexité temporelle de O(n) en évitant les opérations de tableau répétées. La complexité spatiale reste de O(n) pour la carte de hachage et la récursion dans la version optimisée. L'approche optimisée est considérablement plus rapide que l'implémentation naïve. En résumé, l'utilisation d'une carte de hachage et de pointeurs d'index apporte des avantages de performance significatifs.