최대 트리(Maximum Tree)는 모든 노드의 값이 자신의 서브트리에 포함된 다른 어떤 값보다 항상 큰 특수한 이진 트리입니다. 리스트 A가 주어졌을 때 이를 기반으로 루트 노드를 생성하는 construct() 메서드가 있다고 가정해 보겠습니다. construct() 메서드는 다음과 같이 동작합니다.
리스트 A가 비어 있으면 null을 반환합니다.
A[i]가 리스트 A에서 가장 큰 원소라면, 그 값을 가지는 루트 노드를 생성합니다.
루트의 왼쪽 자식은 construct([A[0], A[1], ..., A[i-1]])의 결과가 됩니다.
루트의 오른쪽 자식은 construct([A[i+1], A[i+2], ..., A[n-1]])의 결과가 됩니다. (n은 리스트 A의 길이)
루트를 반환합니다.
문제 정의
여기서 주목할 점은 리스트 A가 직접 주어지지 않고, root = construct(A)로 만들어진 루트 노드만 제공된다는 것입니다. 이제 B는 리스트 A에 새로운 값 val을 추가한 복사본이라고 하며, B의 모든 값은 서로 중복되지 않는다고 보장됩니다. 우리의 목표는 construct(B)의 결과를 구하는 것입니다.
예를 들어 삽입할 값이 5이고 입력 트리가 다음과 같다면,
출력되는 트리는 아래와 같습니다.
해결 전략
이 문제는 재귀적으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 최대 트리의 성질을 활용하는 것입니다. 새로운 값 val이 현재 루트의 값보다 크다면, val이 새로운 루트가 되고 기존 트리 전체가 왼쪽 자식으로 내려가야 합니다. 반대로 val이 루트 값보다 작다면 오른쪽 서브트리 쪽으로만 탐색을 계속하면 됩니다.
루트와 val을 인자로 받는 재귀 메서드 solve()를 정의합니다.
트리가 비어 있다면 val 값을 가지는 새 노드를 만들어 반환합니다.
루트의 값이 val보다 작다면:
val 값을 가지는 새 노드 temp를 생성합니다.
temp의 왼쪽 자식으로 기존 루트를 연결합니다.
temp를 반환합니다.
루트의 값이 val보다 크다면, 루트의 오른쪽 자식에 대해 solve(오른쪽 자식, val)을 재귀 호출하여 결과를 연결합니다.
루트를 반환합니다.
이 알고리즘의 시간 복잡도는 최악의 경우 O(n)이며, 트리의 깊이만큼만 탐색하기 때문에 매우 효율적입니다.
C++ 구현 예시
#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 tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue<TreeNode *> q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
}
else {
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr == NULL || curr->val == 0){
cout << "null" << ", ";
}else{
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
if(!root)return new TreeNode(val);
if(root->val < val){
TreeNode* temp = new TreeNode(val);
temp->left = root;
return temp;
}
root->right = insertIntoMaxTree(root->right, val);
return root;
}
};
main(){
vector<int> v = {4,1,3,NULL,NULL,2};
TreeNode *root = make_tree(v);
Solution ob;
tree_level_trav(ob.insertIntoMaxTree(root, 5));
}입력
[4,1,3,null,null,2] 5
출력
[5, 4, 1, 3, null, null, 2]
마무리
위 코드에서 Solution 클래스의 insertIntoMaxTree() 함수가 실제 해결 로직을 담당합니다. 재귀 호출을 통해 오른쪽 경로를 따라 내려가다가, val보다 작은 값을 만나는 순간 새 노드를 생성하고 기존 서브트리를 왼쪽 자식으로 붙이는 방식입니다. 이처럼 최대 트리의 구조적 성질만 잘 이해하면 복잡한 트리 재구성 없이도 손쉽게 새 값을 삽입할 수 있습니다.