LeetCode - 105. 前順序と中順序遍歴から二分木を構築

このテキストでは、前順（preorder）と中順（inorder）走査から二分木（binary tree）を構築するための2つの方法について説明しています。最初の方法は、再帰的なアプローチで、`slice()`と`indexOf()`を使用しますが、これにより時間複雑度がO(n²)になります。この単純な方法では、根ノードを特定し、その位置を中順配列で見つけ、左と右の部分木を再帰的に構築します。繰り返し配列のスライスは、ナイーブな方法で追加のオーバーヘッドを引き起こします。ナイーブなアプローチでは、再帰とスライスされた配列のために、空間複雑度はO(n)です。2番目のアプローチは最適化されており、ハッシュマップとインデックスポインタを使用して効率を向上させています。この最適化された方法では、ハッシュマップを使用して中順走査でのノードインデックスを定数時間で検索します。インデックスポインタはスライスを置き換え、最適化された方法では不要な配列コピーを避けます。最適化されたアプローチは、繰り返し配列操作を避けることで、時間複雑度O(n)を達成します。ハッシュマップと再帰のために、最適化されたバージョンの空間複雑度はO(n)のままです。最適化されたアプローチは、ナイーブな実装よりもはるかに高速です。要約すると、ハッシュマップとインデックスポインタを使用することで、著しいパフォーマンスの向上が得られます。