C++로 구현하는 이진 트리 지그재그(Zigzag) 순회 알고리즘

이 문제에서는 하나의 이진 트리(binary tree)가 주어지며, 우리의 과제는 이 이진 트리를 지그재그(zigzag) 형태로 출력하는 것입니다.

문제 이해하기

예시를 통해 문제를 살펴보겠습니다. 다음과 같은 이진 트리가 있다고 가정해 봅시다.

위 이진 트리를 지그재그 방식으로 순회한 결과는 다음과 같습니다.

3    5    1    8    7    0    4

접근 방법

이 문제를 해결하려면 이진 트리를 레벨(level) 단위로 순회해야 하며, 각 레벨이 끝날 때마다 순회 방향을 반대로 뒤집어야 합니다. 즉, 첫 번째 레벨은 왼쪽에서 오른쪽으로, 두 번째 레벨은 오른쪽에서 왼쪽으로 탐색하는 방식입니다.

이를 구현하기 위해 두 개의 스택(current와 next)과 순회 방향을 나타내는 하나의 변수(order)를 사용합니다. 먼저 current 스택에서 노드를 꺼내며 자식 노드들을 next 스택에 삽입합니다. 이때 왼쪽 자식부터 오른쪽 자식 순서로 넣으면 스택의 LIFO(Last In First Out) 특성 때문에 다음 레벨에서는 자동으로 역순으로 출력됩니다.

여기서 order 변수(코드에서는 LtR)가 핵심적인 역할을 하는데, 현재 레벨을 어느 방향(왼쪽→오른쪽 또는 오른쪽→왼쪽)으로 출력할지 결정합니다.

구현 예제

위에서 설명한 해결 방법을 C++로 구현한 프로그램은 다음과 같습니다.

#include <iostream>
#include <stack>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
void zigZagTreeTraversal(struct Node* root){
   if (!root)
      return;
   stack<struct Node*> currentlevel;
   stack<struct Node*> nextlevel;
   currentlevel.push(root);
   bool LtR = true;
   while (!currentlevel.empty()) {
      struct Node* temp = currentlevel.top();
      currentlevel.pop();
      if (temp) {
         cout<<temp->data<<"\t";
         if (LtR) {
            if (temp->left)
               nextlevel.push(temp->left);
            if (temp->right)
               nextlevel.push(temp->right);
         }
         else {
            if (temp->right)
               nextlevel.push(temp->right);
            if (temp->left)
               nextlevel.push(temp->left);
         }
      }
      if (currentlevel.empty()) {
         LtR = !LtR;
         swap(currentlevel, nextlevel);
      }
   }
}
struct Node* insertNode(int data){
   struct Node* node = new struct Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int main() {
   struct Node* root = insertNode(3);
   root->left = insertNode(1);
   root->right = insertNode(5);
   root->left->left = insertNode(8);
   root->left->right = insertNode(7);
   root->right->left = insertNode(0);
   root->right->right = insertNode(4);
   cout << "ZigZag traversal of the given binary tree is \n";
   zigZagTreeTraversal(root);
   return 0;
}

실행 결과

ZigZag traversal of the given binary tree is
3    5    1    8    7    0    4

알고리즘 동작 원리 정리

1. 루트 노드를 current 스택에 삽입하고, 순회 방향 변수 LtR을 true(왼쪽→오른쪽)로 초기화합니다.
2. current 스택이 빌 때까지 노드를 하나씩 꺼내며 값을 출력합니다.
3. LtR이 true면 왼쪽 자식을 먼저, false면 오른쪽 자식을 먼저 next 스택에 삽입합니다.
4. current 스택이 비면 LtR 값을 반전시키고, next 스택과 current 스택을 교체(swap)하여 다음 레벨을 순회합니다.
5. 모든 노드를 출력할 때까지 위 과정을 반복합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로, n은 트리의 전체 노드 개수입니다.