[LeetCode # 95] Unique Binary Search Trees II

주어진 문제는 위와 같다. 트리 노드의 개수인 n 이 주어지면, n 개의 노드를 갖는 BST 들을 찾는 것이다. 이 때, n 개의 노드들은 각각 1 부터 n 까지의 값을 갖는다.

 

BST (Binary Search Tree) 는 기본적으로 각 서브트리에서 루트 노드보다 작은 값들만 루트 노드의 Left 서브 트리에 저장될 수 있고, 루트 노드보다 큰 값들만 루트 노드의 Right 서브 트리에 저장될 수 있다는 특징을 갖는다.

 

이러한 특징을 기반으로 재귀를 활용해 문제를 풀이했다. 풀이 방식은 각 재귀 단계마다 BST 를 구성하려는 값의 범위 start ~ end 가 주어지고 그 범위 내의 값들을 루트 노드로 하는 BST 를 찾는 것이다.

 

간단한 슈도 코드로 이를 표현하자면, 다음과 같다.

recursiveBST(start, end):
	for i in (start, end):
    	leftLists <- recursive_bst(start, i - 1)
        rightLists <- recursive_bst(i + 1, end)
        
        for left in leftLists:
        	for right in rightLists:
            	root <- new node(i)
                
                root.left <- left
                root.right <- right

(start, end) 범위 내에서 각각의 값을 갖는 노드를 루트 노드로 구성하고, 그 값보다 작은 값들을 갖는 서브 트리들과 그 값보다 큰 값들을 갖는 서브 트리들을 각각 루트 노드의 왼쪽 서브 트리, 오른쪽 서브 트리로 구성한다.

 

이러한 풀이 방식을 바탕으로 작성한 소스 코드는 다음과 같다.

 

class Solution {
public:
    vector<TreeNode*> generateTrees(int start, int end) {
        vector<TreeNode*> binarySearchTrees;
        if (start > end) {
            binarySearchTrees.push_back(NULL);
            return binarySearchTrees;
        }
        if (start == end) {
            binarySearchTrees.push_back(new TreeNode(start));
            return binarySearchTrees;
        }
        for (int i = start; i <= end; i++) {
            vector<TreeNode*> leftList = generateTrees(start, i - 1);
            vector<TreeNode*> rightList = generateTrees(i + 1, end);

            for (int l = 0; l < leftList.size(); l++) {
                for (int r = 0; r < rightList.size(); r++) {
                    TreeNode* root = new TreeNode(i);
                    root->left = leftList[l];
                    root->right = rightList[r];

                    binarySearchTrees.push_back(root);
                }
            }
        }

        return binarySearchTrees;
    }

    vector<TreeNode*> generateTrees(int n) {
        return generateTrees(1, n);
    }
};