문제 개요
이 문제에서는 하나의 이진 트리(binary tree)가 주어지며, 이 트리의 지그재그 레벨 순서 순회(zigzag level order traversal) 결과를 출력하는 것이 목표입니다. 여기서 핵심 조건은 순회를 수행할 때 단 하나의 큐(queue)만 사용해야 한다는 점입니다.
먼저 예시를 통해 문제를 이해해 보겠습니다.
출력 결과 −
3 1 7 2 8 9 5
접근 방법
큐 하나만으로 이 문제를 해결하려면, 큐와 함께 구분 플래그(separation flag)와 방향 플래그(direction flag)를 추가로 활용해야 합니다.
전체적인 동작 흐름은 다음과 같습니다.
- 트리를 레벨(level) 단위로 순회하며, 가장 먼저 루트 노드를 큐에 삽입합니다.
- 큐에 있는 각 노드를 처리할 때, 해당 노드의 자식 노드들을 차례대로 큐에 삽입합니다.
- NULL을 만나면 현재 순회 방향을 확인한 뒤, 지정된 방향(왼쪽→오른쪽 또는 오른쪽→왼쪽)에 따라 해당 레벨의 요소들을 출력합니다.
- 마지막 NULL을 만날 때까지 위 과정을 반복합니다.
즉, 홀수 번째 레벨은 왼쪽에서 오른쪽으로, 짝수 번째 레벨은 오른쪽에서 왼쪽으로 방향을 번갈아 바꿔가며 노드 값을 출력하는 방식입니다.
예제 코드
위 알고리즘을 구현한 C++ 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* insertNode(int data) {
struct Node* node = new struct Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
void zigZagTraversal(struct Node* root, int n){
struct Node* queue[2 * n];
int top = -1;
int front = 1;
queue[++top] = NULL;
queue[++top] = root;
queue[++top] = NULL;
int prevFront = 0, count = 1;
while (1) {
struct Node* curr = queue[front];
if (curr == NULL) {
if (front == top)
break;
else {
if (count % 2 == 0) {
for (int i = prevFront + 1; i < front; i++)
cout<<queue[i]->data<<"\t";
}
else {
for (int i = front - 1; i > prevFront; i--)
cout<<queue[i]->data<<"\t";
}
prevFront = front;
count++;
front++;
queue[++top] = NULL;
continue;
}
}
if (curr->left != NULL)
queue[++top] = curr->left;
if (curr->right != NULL)
queue[++top] = curr->right;
front++;
}
if (count % 2 == 0) {
for (int i = prevFront + 1; i < top; i++)
cout<<queue[i]->data<<"\t";
}
else {
for (int i = top - 1; i > prevFront; i--)
cout<<queue[i]->data<<"\t";
}
}
int main() {
struct Node* root = insertNode(3);
root->left = insertNode(1);
root->right = insertNode(7);
root->left->left = insertNode(5);
root->left->right = insertNode(9);
root->right->left = insertNode(8);
root->right->right = insertNode(2);
cout<<"Zig Zag traversal of the tree is :\n";
zigZagTraversal(root, 7);
return 0;
}
출력 결과
Zig Zag traversal of the tree is :
3 1 7 2 8 9 5
정리
이처럼 큐에 NULL을 레벨 구분자(separator)로 삽입하고, 레벨 카운트의 홀짝성에 따라 출력 방향을 전환하면 추가 자료구조 없이도 단일 큐만으로 지그재그 레벨 순회를 효율적으로 구현할 수 있습니다.