하나의 이진 트리가 주어졌을 때, 이를 직렬화(serialize)하고 역직렬화(deserialize)해야 한다고 가정해 봅시다.
직렬화란 데이터 구조나 객체를 일련의 비트(bit) 형태로 변환하여 파일이나 메모리 버퍼에 저장할 수 있게 만드는 과정입니다. 이렇게 저장된 데이터는 나중에 동일한 컴퓨터 환경 또는 전혀 다른 환경에서도 원래의 구조로 복원할 수 있습니다.
따라서 여기서는 이진 트리를 직렬화하고 역직렬화하는 알고리즘을 설계해야 합니다. 이진 트리(binary tree)는 각 노드가 최대 2개의 자식 노드를 가질 수 있는 루트 트리(rooted tree)입니다.
예를 들어 입력이 아래와 같은 트리라면,
출력 결과는 다음과 같습니다.
Serialize: 1 2 3 4 5 N N N N N N
Deserialized Tree: 4 2 5 1 3
접근 방법
이 문제는 BFS(너비 우선 탐색, 레벨 순회) 방식을 활용하면 깔끔하게 해결할 수 있습니다. 트리를 위에서부터 한 레벨씩 순회하면서 값을 문자열로 기록하고, 자식이 없는 위치는 특수 문자 "N"으로 표시하는 것이 핵심입니다.
1. 직렬화(Serialize) 과정
- serialize() 함수는 루트 노드(root)를 인자로 받습니다.
- 결과를 담을 문자열 ret을 빈 문자열로 초기화합니다.
- 큐(queue) q를 하나 선언하고, 루트 노드를 큐에 삽입합니다.
- 큐가 빌 때까지 다음을 반복합니다.
- curr = 큐의 첫 번째 요소를 꺼내고, 해당 요소를 큐에서 제거합니다.
- curr이 NULL이라면 ret에 "N"과 공백을 붙이고, 이후 단계는 건너뛰고 다음 반복으로 넘어갑니다.
- curr이 유효하면 ret에 curr의 값을 추가하고 공백을 붙입니다.
- curr의 왼쪽 자식과 오른쪽 자식을 차례대로 큐의 끝에 삽입합니다.
- 모든 순회가 끝나면 ret을 반환합니다.
2. 역직렬화(Deserialize) 과정
- deserialize() 함수는 직렬화된 문자열(data)을 인자로 받습니다.
- data[0]이 'N'이라면 빈 트리이므로 NULL을 반환합니다.
- 임시 문자열 temp와 문자열 배열 v를 준비합니다.
- i := 0부터 data의 길이까지 반복하며 공백을 기준으로 문자열을 분리해 배열 v에 저장합니다.
- v[0] 값을 가지는 새 노드를 만들어 newRoot로 지정합니다.
- 큐 q를 선언하고 newRoot를 삽입한 뒤, 인덱스 i를 1로 초기화합니다.
- 큐가 비어 있지 않고 i가 v의 크기보다 작은 동안 다음을 반복합니다.
- parent = 큐의 첫 번째 요소를 꺼내고 제거합니다.
- v[i]가 "N"이 아니면 parent의 왼쪽 자식을 v[i] 값으로 새 노드를 만들어 연결하고, 그 노드를 큐에 삽입합니다.
- i를 1 증가시킵니다.
- v[i]가 "N"이 아니면 parent의 오른쪽 자식을 v[i] 값으로 새 노드를 만들어 연결하고, 그 노드를 큐에 삽입합니다.
- i를 1 증가시킵니다.
- 완성된 트리의 루트인 newRoot를 반환합니다.
구현 예시
아래의 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 inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Codec {
public:
string serialize(TreeNode *root) {
string ret = "";
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
TreeNode *curr = q.front();
q.pop();
if (!curr) {
ret += "N";
ret += " ";
continue;
}
ret += to_string(curr->val);
ret += " ";
q.push(curr->left);
q.push(curr->right);
}
return ret;
}
TreeNode *deserialize(string data) {
if (data[0] == 'N')
return NULL;
string temp = "";
vector<string> v;
for (int i = 0; i < data.size(); i++) {
if (data[i] == ' ') {
v.push_back(temp);
temp = "";
continue;
}
temp += data[i];
}
TreeNode *newRoot = new TreeNode(stoi(v[0]));
queue<TreeNode *> q;
q.push(newRoot);
int i = 1;
while (!q.empty() && i < v.size()) {
TreeNode *parent = q.front();
q.pop();
if (v[i] != "N") {
parent->left = new TreeNode(stoi(v[i]));
q.push(parent->left);
}
i++;
if (v[i] != "N") {
parent->right = new TreeNode(stoi(v[i]));
q.push(parent->right);
}
i++;
}
return newRoot;
}
};
main() {
Codec ob;
vector<int> v = {1,2,3,4,5};
TreeNode *root = make_tree(v);
cout << "Given Tree: ";
inord(root);
cout << endl;
string ser = ob.serialize(root);
cout << "Serialize: " << ser << endl;
TreeNode *deser = ob.deserialize(ser);
cout << "Deserialized Tree: ";
inord(root);
}
입력
1,2,3,4,5
출력
Given Tree: 4 2 5 1 3
Serialize: 1 2 3 4 5 N N N N N N
Deserialized Tree: 4 2 5 1 3
실행 결과를 보면, 직렬화된 문자열을 역직렬화했을 때 원래 트리의 중위 순회(inorder traversal) 결과인 4 2 5 1 3이 동일하게 출력되는 것을 확인할 수 있습니다. 이는 직렬화 → 역직렬화 과정을 통해 트리 구조가 손실 없이 완전히 복원되었음을 의미합니다.