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

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

---

문제에서는 inorder 순서로 숫자 배열을 입력으로 준다고는 하지만 생각해보면 이진 탐색트리(BST)를 만드는 것과 같다.

항상 루트부터 탐색하면서 NULL이 나올 때까지 현재 탐색중인 노드보다 작으면 왼쪽 자식, 크면 오른쪽 자식 노드로 탐색해간다.

NULL이면 그 자리에 값을 val로 노드를 만들어 넣으면 된다.

이렇게 하면 O(NlogN) 정도 나온다. (코드는 이 방식으로 짰다.)

사실 입력 값을 다 알고 있으면 굳이 항상 루트 노드부터 탐색하면서 트리를 만들 필요는 없다.

예를 들어 [8,5,1,7,10,12]가 입력값이라고 하자.

inorder이므로 첫 번째 값은 루트 노드이다. 루트 노드보다 작은건 모두 왼쪽 서브트리이고 큰건 오른쪽 서브트리이다.

즉, [8,5,1,7,10,12] 파란색 8은 루트 노드, 빨간색 5, 1, 7은 왼쪽 서브트리, 초록색 10, 12는 오른쪽 서브트리이다.

이를 서브트리들에도 적용하면서 O(N)만에 이진 트리를 만들 수 있다.

---

소스코드 : https://gist.github.com/fpdjsns/74392ef8dd5380de77c8e8e60babe02b