이 문제에서는 하나의 이진 트리(binary tree)가 주어지며, 트리의 루트(root)에서 각 리프(leaf) 노드까지의 모든 경로를 출력해야 합니다. 추가로 밑줄 문자 "_"를 활용하여 각 노드의 상대적인 위치(수평 위치)를 함께 표시해야 합니다.
예시를 통해 문제를 더 자세히 살펴보겠습니다.
입력 −
출력 −
_ _ 3 _ 9 1 _3 9 _7 3 _ 4 _ _ 2 3 9 4 1 7 6 2 3 _ 4 6
문제 해결 접근 방식
이 문제를 해결하기 위해 트리 요소들의 수직 순서(vertical order) 개념을 활용합니다.
위 그림과 같이 각 노드에는 수평 거리(horizontal distance)가 할당됩니다. 루트 노드의 수평 거리는 0이고, 왼쪽으로 이동할 때마다 1씩 감소하며, 오른쪽으로 이동할 때마다 1씩 증가합니다. 이 값을 기준으로 루트에서 리프까지의 경로를 출력하면 됩니다.
알고리즘
1단계: 전위 순회(preorder traversal)를 사용하여 이진 트리를 순회합니다.
순회 과정에서 각 노드의 수평 거리를 계산합니다.
루트의 수평 거리는 0이며, 위 다이어그램과 같은 규칙으로 처리합니다.
2단계: 리프 노드에 도달하면, 지금까지의 경로를 구성한 노드들 중
가장 작은 수평 거리를 기준으로 밑줄 "_"의 개수를 계산하여
상대 위치를 표현하면서 경로를 출력합니다.구현 예제
#include<bits/stdc++.h>
using namespace std;
#define MAX_PATH_SIZE 1000
struct Node{
char data;
Node *left, *right;
};
Node * newNode(char data){
struct Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
struct PATH{
int horizontalDistance;
char key;
};
void printPath(vector < PATH > path, int size){
int minimumhorizontalDistance = INT_MAX;
PATH p;
for (int it=0; it<size; it++){
p = path[it];
minimumhorizontalDistance = min(minimumhorizontalDistance, p.horizontalDistance);
}
for (int it=0; it < size; it++){
p = path[it];
int noOfUnderScores = abs(p.horizontalDistance -minimumhorizontalDistance);
for (int i = 0; i < noOfUnderScores; i++) cout<<"_ ";
cout<<p.key<<endl;
}
cout<<"\nNext Path\n";
}
void printAllRtLPaths(Node *root, vector < PATH > &AllPath, int horizontalDistance, int order ){
if(root == NULL)
return;
if (root->left == NULL && root->right == NULL){
AllPath[order] = (PATH { horizontalDistance, root->data });
printPath(AllPath, order+1);
return;
}
AllPath[order] = (PATH { horizontalDistance, root->data });
printAllRtLPaths(root->left, AllPath, horizontalDistance-1, order+1);
printAllRtLPaths(root->right, AllPath, horizontalDistance+1, order+1);
}
void printRootToLeafPath(Node *root){
if (root == NULL)
return;
vector<PATH> Allpaths(MAX_PATH_SIZE);
printAllRtLPaths(root, Allpaths, 0, 0);
}
int main(){
Node *root = newNode('3');
root->left = newNode('9');
root->right = newNode('4');
root->left->left = newNode('1');
root->left->right = newNode('7');
root->right->left = newNode('6');
root->right->right = newNode('2');
printRootToLeafPath(root);
return 0;
}실행 결과
_ _ 3 _ 9 1 Next Path _ 3 9 _ 7 Next Path 3 _ 4 6 Next Path 3 _ 4 _ _ 2
코드 설명
위 코드의 동작 원리를 단계별로 정리하면 다음과 같습니다.
1. PATH 구조체: 각 노드의 데이터(key)와 해당 노드의 수평 거리(horizontalDistance)를 함께 저장합니다.
2. printAllRtLPaths 함수: 재귀적으로 전위 순회를 수행하면서 현재 노드의 정보를 경로 배열에 저장합니다. 왼쪽 자식으로 내려갈 때는 수평 거리를 1 감소시키고, 오른쪽 자식으로 내려갈 때는 1 증가시킵니다. 자식 노드가 없는 리프 노드에 도달하면 printPath 함수를 호출하여 경로를 출력합니다.
3. printPath 함수: 현재 경로에 포함된 노드들 중 최소 수평 거리를 찾은 뒤, 각 노드의 수평 거리와의 차이만큼 밑줄을 출력하여 노드 간의 상대적 위치를 시각적으로 표현합니다.
이 알고리즘의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)이며, 여기서 n은 트리의 노드 개수입니다.