이진 트리를 주어진 규칙에 따라 m×n 크기의 2차원 문자열 배열 형태로 출력해야 하는 경우가 있습니다. 이 문제를 해결하는 방법을 단계별로 살펴보겠습니다.
출력 규칙
- 행의 개수(m)는 주어진 이진 트리의 높이와 같아야 합니다.
- 열의 개수(n)는 항상 홀수여야 합니다.
- 루트 노드의 값은 첫 번째 행에서 정확히 가운데 위치에 배치해야 합니다. 루트 노드가 위치한 행과 열은 나머지 공간을 두 부분으로 나누는데, 각각 좌하단 영역과 우하단 영역입니다. 좌측 서브트리는 좌하단 영역에, 우측 서브트리는 우하단 영역에 출력합니다. 이때 좌하단 영역과 우하단 영역의 크기는 동일해야 합니다. 한쪽 서브트리가 존재하지 않더라도 다른 쪽 서브트리만큼의 공간은 비워두어야 하며, 양쪽 서브트리 모두 존재하지 않는 경우에는 공간을 남길 필요가 없습니다.
- 사용되지 않는 공간은 모두 빈 문자열("")로 채웁니다.
- 서브트리도 동일한 규칙에 따라 재귀적으로 출력합니다.
예시
입력 트리가 다음과 같다고 가정해 보겠습니다.
루트 노드 1을 중심으로 왼쪽 자식 노드 2, 오른쪽 자식 노드 3이 있고, 노드 2의 오른쪽 자식으로 노드 4가 연결된 구조입니다.
이때 기대되는 출력 결과는 다음과 같습니다.
| 1 | ||||||
| 2 | 3 | |||||
| 4 |
해결 알고리즘
이 문제는 재귀적 분할 정복 방식으로 해결할 수 있습니다. 절차는 다음과 같습니다.
- 노드, 결과 행렬(ret), 현재 레벨(lvl), 좌측 경계(l), 우측 경계(r)를 매개변수로 받는 fill() 메서드를 정의합니다.
- 노드가 null이면 즉시 반환합니다.
- ret[lvl][(l + r) / 2] 위치에 노드 값을 문자열로 저장합니다.
- 왼쪽 자식 노드에 대해 fill(node->left, ret, lvl+1, l, (l+r)/2)를 호출합니다.
- 오른쪽 자식 노드에 대해 fill(node->right, ret, lvl+1, (l+r+1)/2, r)를 호출합니다.
- 메인 메서드에서는 다음을 수행합니다.
- h := 트리의 높이 계산
- leaves = 2^h − 1 (전체 열 개수)
- h × leaves 크기의 행렬을 생성하고 빈 문자열로 초기화
- fill(root, ret, 0, 0, leaves) 호출
- 결과 행렬 ret 반환
핵심 아이디어는 각 노드가 담당하는 열 범위 [l, r)를 관리하고, 그 범위의 중간 지점에 노드 값을 배치한 뒤, 왼쪽 자식에게는 좌측 절반 범위를, 오른쪽 자식에게는 우측 절반 범위를 재귀적으로 넘겨주는 것입니다. 이렇게 하면 트리의 구조가 자연스럽게 2차원 배열에 반영됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = 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;
}
class Solution {
public:
int getHeight(TreeNode* node){
if(!node)return 0;
return 1 + max(getHeight(node->left), getHeight(node->right));
}
void fill(TreeNode* node, vector<vector<string>>& ret, int lvl, int l, int r){
if(!node || node->val == 0)return;
ret[lvl][(l + r) / 2] = to_string(node->val);
fill(node->left, ret, lvl + 1, l, (l + r) / 2);
fill(node->right, ret, lvl + 1, (l + r + 1) / 2, r);
}
vector<vector<string>> printTree(TreeNode* root) {
int h = getHeight(root);
int leaves = (1 << h) - 1;
vector < vector <string> > ret(h, vector <string>(leaves, ""));
fill(root, ret, 0, 0, leaves);
return ret;
}
};
main(){
vector<int> v = {1,2,3,NULL,4};
Solution ob;
TreeNode *root = make_tree(v);
print_vector(ob.printTree(root));
}입력
[1,2,3,null,4]
출력
[[, , , 1, , , ], [, 2, , , , 3, ], [, , 4, , , , ]]
동작 원리 설명
위 코드의 핵심 로직을 살펴보면 다음과 같습니다.
- getHeight(): 트리의 전체 높이를 재귀적으로 계산합니다. 이 값이 곧 출력 행렬의 행 개수가 됩니다.
- printTree(): 높이 h를 구한 후, 열 개수를 2^h − 1로 계산합니다. 포화 이진 트리 기준으로 최악의 경우에도 모든 노드를 배치할 수 있는 크기입니다. 그런 다음 빈 문자열로 초기화된 2차원 벡터를 만들고 fill()을 호출합니다.
- fill(): 현재 노드를 해당 레벨의 열 범위 중앙에 배치하고, 왼쪽 자식에게는 [l, 중앙) 범위를, 오른쪽 자식에게는 [중앙, r) 범위를 할당하며 재귀적으로 내려갑니다.
이 알고리즘의 시간 복잡도는 O(h × 2^h)이며, 여기서 h는 트리의 높이입니다. 공간 복잡도 역시 결과 행렬 크기인 O(h × 2^h)입니다.