이 튜토리얼에서는 C++를 사용하여 이진 트리(Binary Tree)에서 루트 노드부터 리프 노드까지 이어지는 첫 번째 최단 경로를 찾아 출력하는 프로그램을 살펴봅니다.
문제 정의
서로 다른 값으로 구성된 이진 트리가 주어졌을 때, 루트 노드에서 출발하여 리프 노드에 도달하는 여러 경로 중 깊이가 가장 얕은 경로, 즉 지나는 노드의 수가 가장 적은 경로를 찾아 출력해야 합니다.
접근 방법
이 문제는 큐(queue)를 이용한 레벨 순회(Level Order Traversal, BFS)로 효율적으로 해결할 수 있습니다. BFS는 트리를 위쪽 레벨부터 아래로 차례대로 탐색하기 때문에, 순회 과정에서 처음 만나는 리프 노드(자식이 없는 노드)가 곧 루트에서 가장 가까운 리프 노드입니다.
탐색과 동시에 각 노드의 부모 정보를 해시 맵(unordered_map)에 저장해 두면, 목표 리프 노드를 발견하는 즉시 탐색을 종료하고 부모 정보를 거슬러 올라가며 최단 경로를 재구성한 뒤 출력할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
struct Node{
struct Node* left;
struct Node* right;
int data;
};
struct Node* create_node(int data){
struct Node* temp = new Node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void print_spath(int Data, unordered_map<int, int> parent){
if (parent[Data] == Data)
return;
print_spath(parent[Data], parent);
cout << parent[Data] << " ";
}
void leftmost_path(struct Node* root){
queue<struct Node*> q;
q.push(root);
int LeafData = -1;
struct Node* temp = NULL;
unordered_map<int, int> parent;
parent[root->data] = root->data;
while (!q.empty()){
temp = q.front();
q.pop();
if (!temp->left && !temp->right){
LeafData = temp->data;
break;
}
else{
if (temp->left){
q.push(temp->left);
parent[temp->left->data] = temp->data;
}
if (temp->right) {
q.push(temp->right);
parent[temp->right->data] = temp->data;
}
}
}
print_spath(LeafData, parent);
cout << LeafData << " ";
}
int main(){
struct Node* root = create_node(21);
root->left = create_node(24);
root->right = create_node(35);
root->left->left = create_node(44);
root->right->left = create_node(53);
root->right->right = create_node(71);
root->left->left->left = create_node(110);
root->left->left->right = create_node(91);
root->right->right->left = create_node(85);
leftmost_path(root);
return 0;
}실행 결과
21 35 53
결과 분석
예제 트리에서 노드 53은 루트(21)의 오른쪽 자식(35)의 왼쪽 자식으로, 자식이 없는 리프 노드입니다. 53보다 위쪽 레벨에는 리프 노드가 존재하지 않으므로, 최단 경로는 21 → 35 → 53이 됩니다.
복잡도 분석
시간 복잡도는 모든 노드를 최대 한 번씩만 방문하므로 O(N)이며, 공간 복잡도는 큐와 부모 맵에 노드 정보를 저장하므로 O(N)입니다. 여기서 N은 트리의 전체 노드 수입니다.