[LeetCode] 95. Unique Binary Search Trees II

문제 출처: https://leetcode.com/problems/unique-binary-search-trees-ii/

Unique Binary Search Trees II - LeetCode

---

문제

정수 $n$이 주어지면, $1\sim n$의 유니크한 숫자를 갖는 노드를 통해 만들 수 있는 모든 BST(이진 탐색 트리)를 반환하라. 답의 순서는 상관없음.

예제

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Input: n = 1
Output: [[1]]

---

풀이

이진 탐색 트리(BST)의 특징을 기반으로 만들 수 있는 모든 트리를 만드는 방식으로 문제를 해결

 

BST는 트리의 어떤 위치의 노드도, 왼쪽 자식의 구성은 자신보다 작은 값으로 구성되고 반대로 오른쪽 자식은 자신보다 큰 값으로 구성된다는 특징이 있다. 이러한 특징에 따라 다음과 같이 문제를 순차적으로 풀어갈 수 있다.

1. 루트 값이 될 수 있는 후보 중에서 하나의 값을 선택하여 TreeNode로 만든다.
2. 선택한 값을 기준으로 해당 값보다 작은 원소와 큰 원소들을 그룹화한다.
3. 작은 원소의 그룹과 큰 원소의 그룹을 대상으로 만들 수 있는 모든 BST를 구한다.
4. 3에서 구해진 하위 BST를 1에서 만든 노드에 (BST의 규칙에 맞게) 붙이는 것으로 모든 가능한 트리를 만든다.
5. 1의 모든 루트 후보에 대해서 1~4 과정을 반복한다.

위 내용에서 3번의 내용을 보면, BST를 구하는 내용이 있는데, 이는 전체 큰 문제와 사실상 같은 문제를 푸는 것인데 문제의 사이즈가 작아진 형태로 해석할 수 있다. 즉, 재귀 형식으로 이 문제를 접근할 수 있다는 것이다.

var generateTrees = function(n) {
    const A = Array(n).fill(0).map((val, idx) => idx+1);
    
    function buildTree(arr) {
        if (arr.length == 0) {
            return [null]
        }
        
        let answer = []
        
        let candidateOfLeft = [];
        let candidateOfRight = [];
        for (let i = 0; i < arr.length; i++) {
            let root = new TreeNode(arr[i]);
            
            candidateOfLeft = buildTree(arr.slice(0, i));
            candidateOfRight = buildTree(i+1 < arr.length ? arr.slice(i+1) : []);
            
            for (let left of candidateOfLeft){
                root.left = left;
                for (let right of candidateOfRight) {
                    root.right = right;
                    
                    answer.push(JSON.parse(JSON.stringify(root)))
                }
            }
        }
        
        return answer;
    }
    
    return buildTree(A);
};

 

 

Github: 95.js

GitHub - opwe37/Algorithm-Study