서로 다른 값을 가지는 노드들로 구성된 이진 트리가 주어지고, 그 트리 안에서 경로를 출력하려는 두 개의 노드가 주어집니다.
예시 — 노드 140에서 노드 211 사이의 경로를 출력하고 싶다면, 결과는 다음과 같아야 합니다.
Output: 140->3->10->211
접근 방법
핵심 아이디어는 루트 노드에서 두 노드 각각까지의 경로를 찾아 path1과 path2라는 두 개의 벡터(또는 배열)에 저장하는 것입니다.
이때 고려해야 하는 경우는 크게 두 가지입니다.
- 두 노드가 서로 다른 서브트리에 속한 경우 — 한 노드는 왼쪽 서브트리에, 다른 노드는 오른쪽 서브트리에 있는 상황입니다. 이 경우 루트 노드가 node1에서 node2로 이어지는 경로의 중간에 반드시 존재하므로, path1을 역순으로 출력한 뒤 path2를 이어서 출력하면 원하는 경로를 얻을 수 있습니다.
- 두 노드가 같은 서브트리에 속한 경우 — 두 노드가 모두 왼쪽 또는 오른쪽 서브트리에 있는 상황입니다. 루트에서 두 노드까지의 경로는 특정 교차점 이전까지는 동일한 경로를 공유하게 됩니다. 따라서 이 교차점을 먼저 찾은 뒤, 그 지점부터 앞선 경우와 같은 방식으로 노드를 출력해야 합니다.
알고리즘
START
STEP 1-> struct Node 정의
int data와 Node *left, *right 멤버 포함
STEP 2-> 트리 노드 생성 함수 struct Node* tree(int data) 정의
FUNCTION bool path(Node* root, vector& arr, int x)
STEP 1-> root가 NULL이면
false 반환
END IF
STEP 2-> arr.push_back(root->data) 실행
root->data == x이면
true 반환
END IF
STEP 3-> path(root->left, arr, x) || path(root->right, arr, x)가 참이면
true 반환
STEP 4-> arr.pop_back() 실행
false 반환
END FUNCTION
FUNCTION void printPath(Node* root, int n1, int n2)
STEP 1-> vector<int> path1 선언
STEP 2-> vector<int> path2 선언
STEP 3-> path(root, path1, n1) 호출
STEP 4-> path(root, path2, n2) 호출
STEP 5-> intersection = -1, i = 0, j = 0으로 초기화
STEP 6-> i != path1.size() || j != path2.size()인 동안 반복
i == j && path1[i] == path2[j]이면
i를 1 증가
j를 1 증가
그렇지 않으면
intersection = j - 1로 설정
반복 종료(BREAK)
END IF
END WHILE
STEP 7-> i = path1.size() - 1부터 시작해 i > intersection인 동안 i-- 하며 path1[i] 출력
END FOR
STEP 8-> i = intersection부터 시작해 i < path2.size()인 동안 i++ 하며 path2[i] 출력
END FOR
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// 이진 트리 노드의 구조체 정의
struct Node {
int data;
Node *left, *right;
};
struct Node* tree(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// 루트에서 값 x를 가진 노드까지의 경로를 arr에 저장하는 함수
bool path(Node* root, vector<int>& arr, int x){
if (!root)
return false;
// 현재 노드의 값을 'arr'에 추가
arr.push_back(root->data);
// 목표 노드를 찾았다면 true 반환
if (root->data == x)
return true;
if (path(root->left, arr, x) || path(root->right, arr, x))
return true;
arr.pop_back();
return false;
}
// 이진 트리에서 임의의 두 노드 사이의 경로를 출력하는 함수
void printPath(Node* root, int n1, int n2){
// 경로를 저장할 벡터 선언
vector<int> path1;
vector<int> path2;
path(root, path1, n1);
path(root, path2, n2);
int intersection = -1;
int i = 0, j = 0;
while (i != path1.size() || j != path2.size()) {
if (i == j && path1[i] == path2[j]) {
i++;
j++;
} else {
intersection = j - 1;
break;
}
}
// 구한 경로 출력
for (int i = path1.size() - 1; i > intersection; i--)
cout << path1[i] << " ";
for (int i = intersection; i < path2.size(); i++)
cout << path2[i] << " ";
}
int main(){
// 이진 트리 생성
struct Node* root = tree(1);
root->left = tree(2);
root->left->left = tree(4);
root->left->left->left = tree(6);
root->left->right = tree(5);
root->left->right->left = tree(7);
root->left->right->right = tree(8);
root->right = tree(3);
root->right->left = tree(9);
root->right->right = tree(10);
int node1 = 5;
int node2 = 9;
printPath(root, node1, node2);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
5 2 1 3 9
노드 5에서 노드 9로 가는 경로는 두 노드의 최소 공통 조상(LCA)인 루트 노드 1을 거쳐 5 → 2 → 1 → 3 → 9 순서로 출력됩니다.
복잡도 분석
경로 탐색 함수(path)는 트리의 각 노드를 최대 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 트리의 노드 수입니다. 또한 두 노드까지의 경로를 저장하기 위해 최악의 경우 O(n)의 추가 공간이 필요합니다.