반응형
주어진 문제는 위와 같다. 트리 노드의 개수인 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);
}
};'Algorithm > LeetCode' 카테고리의 다른 글
| [LeetCode # 68] Text Justification (0) | 2021.09.07 |
|---|---|
| [LeetCode # 1629] Slowest Keys (0) | 2021.09.07 |
| [LeetCode # 153] Find Minimum in Rotated Sorted Array (0) | 2021.09.01 |
| [LeetCode # 60] Permutation Sequence (0) | 2021.09.01 |
| [LeetCode # 135] Candy (0) | 2021.06.27 |
