[leetcode][1008] Construct Binary Search Tree from Preorder Traversal

문제 : https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

---

이진 탐색 트리를 전위순회한 결과 배열을 입력값으로 받을 때, 이진 탐색트리를 구한 뒤 루트를 반환하라.

---

이진탐색트리는 왼쪽 자식 서브트리들의 노드는 루트 노드보다 작고, 오른쪽 자식 서브트리들의 노드들은 루트 노드보다 크다.

이를 이용해서 왼쪽 자식들과 오른쪽 자식들을 구분할 수 있다.

예를 들어, [8,5,1,7,10,12] 일때. 전위 순회이므로 8은 루트가 된다.

8 이후의 배열들 중 8보다 작은 값들은 [5, 1, 7] 이고 8보다 큰 값들은 [10, 12] 이다.

전위 순회이므로 나눈 배열들 중 가장 앞에 있는 요소가 루트의 왼쪽, 오른쪽 자식노드들이 된다.

즉, 8이 루트 노드, 5가 루트 노드의 왼쪽 자식 노드. 10이 루트 노드의 오른쪽 자식 노드가 된다.

다시 나눈 배열들을 입력 배열이라 치고 탐색해보면 [5, 1, 7]은 5가 루트 노드이고 [1], [7]로 나뉜다. 이를 5 노드의 왼쪽, 오른쪽 자식 노드에 각자 추가한다. 더 추가할 배열이 없으므로 탐색 종료.

이제 [10, 12] 배열을 마저 붙여준다. [10, 12]는 루트 노드가 10이고 왼쪽 자식노드는 존재하지 않는다.(10보다 작은 수가 없음.) 12는 오른쪽 자식 노드가 되므로 10 노드의 오른쪽 자식 노드로 추가한다.

분할 정복 문제라고 봐도 되겠다.

 

시간복잡도는 O(NlogN). N = |preorder|

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1008.%20Construct%20Binary%20Search%20Tree%20from%20Preorder%20Traversal.cpp