문제 소개
몇 개의 노드로 구성된 이진 트리가 있다고 가정해 보겠습니다. 이때 구해야 할 것은 루트(root) 노드에서 특정 노드 u까지의 거리, 즉 두 노드를 연결하는 경로의 길이입니다.
예를 들어 다음과 같은 이진 트리가 있다고 합시다.
위 트리에서 루트(1)와 노드 6 사이의 거리는 2입니다. 루트 → 3 → 6 순서로 두 개의 간선을 지나기 때문입니다. 마찬가지로 루트와 노드 8 사이의 거리는 3이 됩니다.
접근 방식
이 문제는 재귀(recursion) 기반 탐색으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 노드가 NULL이면 -1을 반환합니다. 해당 경로에서는 대상 노드를 찾지 못했다는 의미입니다.
- 현재 노드의 값이 찾고자 하는 값 x와 같으면 그 지점에서 탐색을 종료합니다.
- 찾지 못한 경우 왼쪽 하위 트리와 오른쪽 하위 트리를 순서대로 재귀적으로 탐색합니다.
- 하위 트리에서 노드를 발견하면, 재귀 호출이 되돌아오는 과정에서 매 레벨마다 거리에 1씩 더해져 최종적으로 루트까지의 거리가 계산됩니다.
C++ 구현 예제
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int getDistance(Node *root, int x) {
if (root == NULL)
return -1;
int dist = -1;
if ((root->data == x) || (dist = getDistance(root->left, x)) >= 0 || (dist = getDistance(root->right, x)) >= 0)
return dist + 1;
return dist;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
root->right->left->right = getNode(8);
cout <<"Distance from root to node 6 is: " << getDistance(root,6);
cout << "\nDistance from root to node 8 is: " << getDistance(root,8);
}
실행 결과
Distance from root to node 6 is: 2 Distance from root to node 8 is: 3
코드 설명
핵심 함수인 getDistance()의 동작 원리를 자세히 살펴보겠습니다.
- 기저 조건: root가 NULL이면 -1을 반환하여 이 경로에는 대상 노드가 존재하지 않음을 알립니다.
- 거리 누적: 현재 노드의 값이 x와 일치하거나, 왼쪽 또는 오른쪽 하위 트리 탐색 결과가 0 이상이면 dist + 1을 반환합니다. 덕분에 재귀 호출이 루트로 되돌아오는 동안 각 레벨마다 거리가 1씩 증가합니다.
- 시간 복잡도: 최악의 경우 트리의 모든 노드를 방문해야 하므로 O(n)입니다. 여기서 n은 전체 노드의 개수입니다.