이 문제에서는 하나의 이진 트리가 주어지며, 각 레벨(층)에 속한 노드들을 값을 기준으로 정렬된 순서로 모두 출력해야 합니다.
예시를 통해 개념을 더 쉽게 이해해 보겠습니다.
입력 예시
루트 노드의 값이 12이고, 왼쪽 자식은 98, 오른쪽 자식은 34인 이진 트리가 주어졌다고 가정합니다. 그 아래 레벨에는 76, 5, 12, 45가 위치합니다.
출력 결과
12 34 98 5 12 45 76
위 출력에서 볼 수 있듯이 각 레벨의 노드 값들은 왼쪽에서 오른쪽 순서가 아니라, 오름차순으로 정렬되어 출력됩니다.
접근 방법
이 문제를 해결하려면 트리의 각 레벨을 순회하면서 해당 레벨의 값을 정렬된 순서로 출력해야 합니다. 이를 위해 다음과 같은 자료구조를 활용합니다.
- 큐(Queue): 레벨 순회(BFS)를 위해 노드를 순서대로 저장합니다.
- 우선순위 큐(Priority Queue) 2개: 하나는 현재 레벨의 값들을, 다른 하나는 다음 레벨의 값들을 오름차순으로 관리합니다.
또한 큐에 NULL 구분자(separator)를 삽입하여 서로 다른 레벨을 구분합니다. 한 레벨의 순회가 끝나면 현재 레벨 우선순위 큐와 다음 레벨 우선순위 큐를 맞바꿔(swap) 처리를 이어갑니다.
구현 코드
아래는 위 로직을 C++로 구현한 예제입니다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
void printLevelElements(Node* root){
if (root == NULL)
return;
queue<Node*> q;
priority_queue<int, vector<int>, greater<int> > current_level;
priority_queue<int, vector<int>, greater<int> > next_level;
q.push(root);
q.push(NULL);
current_level.push(root->data);
while (q.empty() == false) {
int data = current_level.top();
Node* node = q.front();
if (node == NULL) {
q.pop();
if (q.empty())
break;
q.push(NULL);
cout << "\n";
current_level.swap(next_level);
continue;
}
cout << data << " ";
q.pop();
current_level.pop();
if (node->left != NULL) {
q.push(node->left);
next_level.push(node->left->data);
}
if (node->right != NULL) {
q.push(node->right);
next_level.push(node->right->data);
}
}
}
Node* insertNode(int data){
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main(){
Node* root = insertNode(12);
root->left = insertNode(98);
root->right = insertNode(34);
root->left->left = insertNode(76);
root->left->right = insertNode(5);
root->right->left = insertNode(12);
root->right->right = insertNode(45);
cout << "Elements at each Level of binary tree are \n";
printLevelElements(root);
return 0;
}실행 결과
Elements at each Level of binary tree are 12 34 98 5 12 45 76
동작 원리 정리
- 루트 노드를 큐에 넣고, 레벨 구분을 위한
NULL을 함께 삽입합니다. - 큐에서 노드를 하나씩 꺼내며, 현재 레벨 우선순위 큐의 최솟값(top)을 출력합니다.
- 노드의 자식들이 있으면 큐에 추가하고, 자식들의 값은 다음 레벨 우선순위 큐에 삽입합니다.
NULL을 만나면 한 레벨이 끝난 것이므로 줄바꿈을 하고, 두 우선순위 큐를 swap하여 다음 레벨을 처리합니다.
이 방식은 시간 복잡도 측면에서 각 레벨의 노드 수를 n이라 할 때 우선순위 큐 연산으로 인해 O(n log n)의 비용이 들지만, 레벨 순회와 정렬을 한 번의 순회로 동시에 처리할 수 있다는 장점이 있습니다.