정수 배열이 하나 주어져 있다고 가정해 보겠습니다. 배열의 모든 원소는 중복 없이 고유한 값입니다. 이 배열을 바탕으로 만들어지는 최대 트리(Maximum Tree)는 다음과 같은 규칙에 따라 정의됩니다.
루트(root)에는 배열에서 가장 큰 값이 위치합니다.
왼쪽 서브트리는 최댓값을 기준으로 나뉜 왼쪽 부분 배열로부터 만들어진 최대 트리입니다.
오른쪽 서브트리는 최댓값을 기준으로 나뉜 오른쪽 부분 배열로부터 만들어진 최대 트리입니다.
즉, 주어진 배열로 최대 이진 트리(maximum binary tree)를 구성해야 합니다. 예를 들어 입력이 [3,2,1,6,0,5]라면 결과 트리는 다음과 같습니다.
문제 해결 접근 방법
이 문제는 분할 정복(divide and conquer) 기법으로 재귀적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
solve()라는 메서드를 정의합니다. 이 함수는 배열과 left, right 두 인덱스를 인자로 받으며 다음과 같이 동작합니다.
left > right이면 null을 반환합니다. (해당 구간에 더 이상 원소가 없다는 의미)
maxIndex := left, maxVal := nums[left]로 초기화합니다.
i를 left + 1부터 right까지 순회하며 다음을 확인합니다.
만약 maxVal < nums[i]라면 maxVal := nums[i], maxIndex := i로 갱신합니다.
maxVal 값을 갖는 노드를 새로 생성합니다.
노드의 왼쪽 자식 := solve(nums, left, maxIndex - 1)
노드의 오른쪽 자식 := solve(nums, maxIndex + 1, right)
생성한 노드를 반환합니다.
메인 함수에서는 solve(nums, 0, 배열 길이 - 1) 형태로 호출하여 전체 트리를 얻을 수 있습니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
} else {
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
} else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
void inord(TreeNode *root){
if(root != NULL){
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* solve(vector <int>& nums, int left, int right){
if(left>right)
return NULL;
int maxIndex = left;
int maxVal = nums[left];
for(int i = left + 1; i <= right; i++){
if(maxVal < nums[i]){
maxVal = nums[i];
maxIndex = i;
}
}
TreeNode* node = new TreeNode(maxVal);
node->left = solve(nums, left, maxIndex - 1);
node->right = solve(nums, maxIndex + 1, right);
return node;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return solve(nums, 0, nums.size() - 1);
}
};
main(){
vector<int> v = {3,2,1,6,0,5};
Solution ob;
inord(ob.constructMaximumBinaryTree(v));
}
입력
[3,2,1,6,0,5]
출력
3 2 1 6 0 5
시간 복잡도
위 방식은 재귀 호출 시마다 해당 구간에서 최댓값을 찾기 위해 선형 탐색을 수행합니다. 따라서 최악의 경우(예: 배열이 오름차순으로 정렬된 경우) 시간 복잡도는 O(n²)가 됩니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하며, 최악의 경우 O(n)입니다. 참고로 단조 스택(monotonic stack)을 활용하면 O(n) 시간 안에 동일한 트리를 구성할 수도 있습니다.