리트코드 - 105. 프리오더 및 순서 순회 탐색으로 이진 트리 구축하기

이 글은 전위 순회(preorder traversal)와 중위 순회(inorder traversal) 결과를 이용하여 이진 트리를 구성하는 두 가지 방법을 설명합니다. 첫 번째 방법은 단순한 재귀적 접근 방식으로, `slice()`와 `indexOf()`를 사용하여 O(n²)의 시간 복잡도를 가집니다. 이 단순한 방법은 루트를 식별하고, 중위 순회 배열에서 해당 위치를 찾아, 좌우 하위 트리를 재귀적으로 구성합니다. 단순한 방법에서는 반복적인 배열 슬라이싱이 추가적인 오버헤드를 발생시킵니다. 단순한 접근 방식은 재귀 호출과 슬라이싱된 배열 때문에 O(n)의 공간 복잡도를 가집니다. 두 번째 방법은 해시 맵과 인덱스 포인터를 활용하여 효율성을 높였습니다. 이 최적화된 방법은 중위 순회에서 노드 인덱스를 상수 시간 내에 조회하기 위해 해시 맵을 사용합니다. 인덱스 포인터는 슬라이싱을 대체하여 최적화된 방법에서 불필요한 배열 복사를 피합니다. 최적화된 접근 방식은 반복적인 배열 연산을 피함으로써 O(n)의 시간 복잡도를 달성합니다. 해시 맵과 재귀 호출로 인해 공간 복잡도는 최적화된 버전에서도 O(n)으로 유지됩니다. 최적화된 접근 방식은 단순 구현보다 훨씬 빠릅니다. 요약하자면, 해시 맵과 인덱스 포인터를 사용하면 상당한 성능 이점을 얻을 수 있습니다.