개요
이진 트리(binary tree)가 주어졌을 때, 프로그램은 루트(root)에서 리프(leaf) 노드까지 이어지는 여러 경로를 모두 찾아 출력해야 합니다. 여기서 핵심 조건은 재귀(recursion)를 사용하지 않는 것입니다.
재귀 호출 없이 문제를 해결하기 위해 트리를 반복(iterative) 방식으로 순회합니다. 이때 STL의 map 컨테이너를 활용하여 각 자식 노드가 자신의 부모 노드를 가리키도록 정보를 저장합니다. 순회 과정에서 리프 노드를 만나면, 맵에 기록된 부모 포인터를 따라 거슬러 올라가 루트부터 해당 리프까지의 경로를 출력할 수 있습니다.
예를 들어 위와 같은 이진 트리에서 루트에서 리프까지 도달할 수 있는 경로는 다음과 같이 여러 개 존재합니다.
10 -> 3 -> 140 10 -> 3 -> 162 10 -> 211 -> 100 10 -> 211 -> 146
따라서 프로그램은 주어진 이진 트리에 대해 위와 같은 모든 경로를 출력해야 합니다.
알고리즘
시작
1단계 -> 노드 구조체 생성
struct Node
struct node *left, *right
int data
끝
2단계 -> 새 노드 생성 함수
node* newnode(int data)
node->data = data
node->left = node->right = NULL;
return (node)
3단계 -> 경로 계산 함수 작성
void calculatePath(Node* curr, map<Node*, Node*> first)
STL stack<Node*> stk 생성
While(curr) 반복
stk.push(curr)
curr = first[curr]
끝
While(!stk.empty()) 반복
curr = stk.top()
stk.pop()
curr->data 출력
끝
4단계 -> 리프 노드 탐색 함수 작성
void leaf(Node* root)
IF root == NULL
Return
끝
STL stack<Node*> stc 생성
stc.push(root)
STL map<Node*, Node*> prnt 생성
prnt[root] = NULL
While(!stc.empty()) 반복
Node* curr = stc.top()
stc.pop()
IF !(curr->left) && !(curr->right)
calculatePath(curr, prnt)
끝
IF curr->right
prnt[curr->right] = curr
stc.push(curr->right)
끝
IF curr->left
prnt[curr->left] = curr
stc.push(curr->left)
끝
끝
종료예제 코드
#include <bits/stdc++.h>
using namespace std;
// 노드 구조체 정의
struct Node{
int data;
struct Node *left, *right;
};
// 새 노드를 생성하는 함수
Node* newNode(int data){
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
// 경로를 계산하여 출력하는 함수
void calculatePath(Node* curr, map<Node*, Node*> first){
stack<Node*> stk;
while (curr){
stk.push(curr);
curr = first[curr];
}
while (!stk.empty()){
curr = stk.top();
stk.pop();
cout << curr->data << " ";
}
cout << endl;
}
// 리프 노드를 찾아가는 함수
void leaf(Node* root){
if (root == NULL)
return;
stack<Node*> stc;
stc.push(root);
map<Node*, Node*> prnt;
prnt[root] = NULL;
while (!stc.empty()){
Node* curr = stc.top();
stc.pop();
if (!(curr->left) && !(curr->right))
calculatePath(curr, prnt);
if (curr->right){
prnt[curr->right] = curr;
stc.push(curr->right);
}
if (curr->left){
prnt[curr->left] = curr;
stc.push(curr->left);
}
}
}
int main(){
Node* root = newNode(67); // 노드를 삽입하여 트리 생성
root->left = newNode(34);
root->right = newNode(89);
root->left->left = newNode(23);
root->left->right = newNode(95);
root->right->left = newNode(12);
leaf(root); // leaf 함수 호출
return 0;
}출력 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
67 34 23 67 34 95 67 89 12
동작 원리 정리
이 접근 방식의 핵심은 두 가지입니다. 첫째, 스택(stack)을 이용한 반복적 순회로 재귀 호출을 대체합니다. 둘째, map<Node*, Node*> 형태의 부모 포인터 맵을 유지하여 어느 리프 노드에서든 루트까지의 경로를 역추적할 수 있습니다. 리프 노드를 발견하면 calculatePath 함수가 부모 맵을 따라 거슬러 올라가며 노드를 스택에 차곡차곡 담고, 이후 스택에서 꺼내는 순서대로 출력하기 때문에 루트에서 리프 방향의 올바른 경로가 완성됩니다.
시간 복잡도는 트리 순회에 O(n)이 소요되고, 각 리프마다 경로 길이만큼 역추적 비용이 추가되므로 전체적으로 O(n × h)(h는 트리의 높이)입니다. 공간 복잡도는 부모 맵과 스택 저장을 위해 O(n)입니다.