[LeetCode] 1008. Construct Binary Search Tree from Preorder Traversal

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

Construct Binary Search Tree from Preorder Traversal - LeetCode

---

문제

BST(이진 탐색 트리)를 전위 순회한 결과 배열이 주어지면, 트리를 만들고 그 루트 노드를 반환하라.

 

주어진 테스트 케이스에는 항상 가능한 이진 탐색 트리를 찾을 수 있음이 보장된다.

예제

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Input: preorder = [1,3]
Output: [1,null,3]

---

풀이

이 문제는 정복 분할(Divid and Conquer) 방식으로 접근할 수 있습니다.

 

전위 순회의 특성으로 결과 배열의 첫 번째 인덱스의 값은 최상위 루트가 됩니다. 이 값을 기준으로 나머지 값들을 이진 탐색 트리의 기준에 맞게 두 파트(root보다 작은 값, root보다 큰 값)로 나눌 수 있습니다.

이렇게 나뉜 두 파트에 대해서 각각 이전과 마찬가지로 첫 번째 값은 루트로 하고 나머지를 두 부분으로 나누는 과정을 반복할 수 있습니다.

 

전체 과정을 그림으로 표현하면 아래와 같습니다. 각 단계에서 root로 설정되는 값만 추출하게 되면 예제에서 보여주는 이진 탐색 트리의 모습과 동일한 것을 알 수 있습니다.

이러한 과정을 코드로 작성하면 다음과 같습니다.

var bstFromPreorder = function(preorder) {
    let answer = null;
    
    function buildTree(arr) {
        if (arr.length == 0) { return null; }
        
        const left = arr.filter(val => val < arr[0]);
        const right = arr.filter(val => val > arr[0]);
        
        return new TreeNode(arr[0], buildTree(left), buildTree(right));
    }
    
    answer = buildTree(preorder);

    return answer;
};

알고리즘의 시간 복잡도를 계산하면, buildTree(arr)는 한번 호출할 때마다 매개변수로 주어지는 arr을 탐색해야 하므로 $O(n)$의 시간이 걸립니다. 이 buildTree(arr)이 preorder의 길이만큼 호출되기 때문에 전체 시간 복잡도는 $O(n^2)$이라 할 수 있습니다. 

 

Github: 1008.js

GitHub - opwe37/Algorithm-Study