이진 트리가 하나 주어져 있고, 여기서 리프 노드(자식이 없는 노드)들을 서로 쌍으로 교환하는 것이 우리의 과제입니다. 예를 들어 다음과 같습니다.
입력 −
출력 −
이 문제는 두 개의 포인터를 유지하면서 인접한 두 리프 노드를 차례로 가리키게 하고, 해당 노드들의 값을 서로 교환하는 방식으로 해결할 수 있습니다.
문제 해결 접근 방법
이 접근 방식에서는 트리를 순회하면서 리프 노드를 찾고, 지금까지 발견한 리프 노드의 개수를 세는 카운터를 함께 관리합니다. 핵심 아이디어는 다음과 같습니다.
- 카운터가 홀수일 때 : 현재 발견한 리프 노드를 첫 번째 포인터에 저장해 둡니다. 아직 쌍이 완성되지 않은 상태입니다.
- 카운터가 짝수일 때 : 새로 발견한 리프 노드가 앞서 저장한 노드와 한 쌍을 이루므로, 두 노드의 데이터를 교환합니다.
이 과정을 트리 전체에 대해 반복하면 모든 리프 노드가 인접한 노드끼리 쌍으로 교환됩니다. 트리의 각 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(N)(N은 노드 수)이며, 재귀 호출 스택으로 인해 공간 복잡도는 트리의 높이 H에 비례하는 O(H)입니다.
C++ 예제 코드
위 접근 방법을 구현한 C++ 코드
#include <bits/stdc++.h>
using namespace std;
struct Node{ // 트리 노드의 구조체
int data;
struct Node *left, *right;
};
void Swap(Node **a, Node **b){ // 노드 교환 유틸리티 함수
Node *temp = *a;
*a = *b;
*b = temp;
}
/********리프 노드 교환을 위한 포인터********/
Node **firstleaf;
Node **secondleaf;
void SwapTheLeafNodes(Node **root, int &count){ // 리프 노드를
// 교환하기 위한 재귀 함수
if (!(*root)) // 루트가 null이면 그대로 반환
return;
if (!(*root)->left && !(*root)->right){ // 리프 노드 판별 조건
secondleaf = root; // 먼저 두 번째 포인터가 이 노드를 가리키도록 함
count++; // 카운트 증가
if (count % 2 == 0) // 카운트가 짝수면 쌍이 완성된 것이므로 두 노드를 교환
Swap(firstleaf, secondleaf);
else // 카운트가 홀수면 아직 첫 번째 노드만 발견한 상태
firstleaf = secondleaf;
}
if ((*root)->left)
SwapTheLeafNodes(&(*root)->left, count);
if ((*root)->right)
SwapTheLeafNodes(&(*root)->right, count);
}
Node* newNode(int data){ // 새 노드를 초기화하는 함수
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printInorder(Node* node){ // 중위 순회 함수
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main(){
/* 이진 트리 생성 */
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
root->right->right = newNode(8);
root->right->left->left = newNode(6);
root->right->left->right = newNode(7);
root->right->right->left = newNode(9);
root->right->right->right = newNode(10);
cout << "Inorder traversal before swap:\n";
printInorder(root);
cout << "\n";
int count = 0; // 리프 노드를 추적하기 위한 카운터
SwapTheLeafNodes(&root, count); // 노드 교환 수행
cout << "Inorder traversal after swap:\n";
printInorder(root);
cout << "\n";
return 0;
}
실행 결과
Inorder traversal before swap: 4 2 1 6 5 7 3 9 8 10 Inorder traversal after swap: 6 2 1 4 5 9 3 7 8 10
코드 상세 설명
위 코드에서는 리프 노드를 추적하기 위해 두 개의 포인터(firstleaf, secondleaf)를 사용합니다. 트리를 재귀적으로 순회하다가 리프 노드를 만나면, 먼저 두 번째 포인터가 해당 노드를 가리키도록 하고 count 변수를 1 증가시킵니다.
이때 count가 짝수라면 앞서 저장해 둔 노드와 한 쌍을 이루게 되므로 Swap 함수를 호출해 두 노드의 값을 교환합니다. 반대로 count가 홀수라면 아직 쌍의 첫 번째 원소만 발견한 상태이므로, 현재 노드를 첫 번째 포인터에 저장해 두었다가 다음 리프 노드가 발견될 때 교환에 사용합니다. 함수는 이러한 방식으로 트리 전체를 순회하며 리프 노드들을 쌍별로 교환합니다.
main 함수에서는 예제용 이진 트리를 생성한 뒤, 교환 전과 후의 중위 순회(inorder traversal) 결과를 각각 출력하여 리프 노드의 값들이 실제로 서로 바뀌었는지 확인합니다.
마무리
이 튜토리얼에서는 이진 트리에서 리프 노드를 쌍별로 교환하는 문제를 해결해 보았습니다. 문제 해결을 위한 C++ 프로그램과 함께, 두 포인터와 카운터를 활용한 효율적인 접근 방식도 자세히 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되었기를 바랍니다.