문제 개요
이진 트리가 하나 주어져 있고, 각 리프(잎) 노드는 서로 다른 깊이의 레벨에 위치한다고 가정해 보겠습니다. 여기에 특정 노드를 가리키는 포인터가 추가로 주어지는데, 우리가 구해야 할 것은 바로 그 노드로부터 가장 가까운 리프 노드까지의 거리입니다.
아래와 같은 트리를 예로 들어 살펴보겠습니다.
이 트리에서 리프 노드는 2, -2, 6 세 개입니다. 만약 포인터가 노드 -5를 가리키고 있다면, -5에서 가장 가까운 리프 노드는 거리 1만큼 떨어진 곳에 위치합니다.
해결 접근 방법
이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.
① 하향 탐색 — 주어진 노드 x를 루트로 하는 서브트리를 먼저 순회하여, 그 안에서 가장 가까운 리프까지의 거리를 찾아 저장합니다.
② 상위 경유 탐색 — 루트부터 트리를 순회하면서 x의 위치를 찾습니다. x가 어느 노드의 왼쪽 서브트리에 속해 있다면 그 노드의 오른쪽 서브트리를 탐색하여, 위쪽으로 우회했을 때 더 가까운 리프가 존재하는지 확인합니다. x가 오른쪽 서브트리에 있는 경우에는 반대로 왼쪽 서브트리를 탐색합니다.
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;
}
void getLeafDownward(Node *root, int level, int *minDist) {
if (root == NULL)
return ;
if (root->left == NULL && root->right == NULL) {
if (level < (*minDist))
*minDist = level;
return;
}
getLeafDownward(root->left, level+1, minDist);
getLeafDownward(root->right, level+1, minDist);
}
int getFromParent(Node * root, Node *x, int *minDist) {
if (root == NULL)
return -1;
if (root == x)
return 0;
int l = getFromParent(root->left, x, minDist);
if (l != -1) {
getLeafDownward(root->right, l+2, minDist);
return l+1;
}
int r = getFromParent(root->right, x, minDist);
if (r != -1) {
getLeafDownward(root->left, r+2, minDist);
return r+1;
}
return -1;
}
int minimumDistance(Node *root, Node *x) {
int minDist = INT8_MAX;
getLeafDownward(x, 0, &minDist);
getFromParent(root, x, &minDist);
return minDist;
}
int main() {
Node* root = getNode(4);
root->left = getNode(2);
root->right = getNode(-5);
root->right->left = getNode(-2);
root->right->right = getNode(6);
Node *x = root->right;
cout << "Closest distance of leaf from " << x->data <<" is: " << minimumDistance(root, x);
}
코드 설명
- getLeafDownward(): 특정 노드에서 아래 방향으로 내려가며 리프 노드를 탐색하는 함수입니다. 리프에 도달할 때마다 현재 레벨(level)이 기존 최소 거리(minDist)보다 작으면 값을 갱신합니다.
- getFromParent(): 루트에서 출발해 x 노드의 위치를 재귀적으로 찾습니다. x를 발견하면 0을 반환하고, 호출 스택을 따라 한 단계씩 올라가며 형제 서브트리 쪽 리프까지의 거리도 함께 고려합니다. 이때 형제 자식에서 리프까지의 거리는 (x까지의 거리 + 2)부터 시작됩니다.
- minimumDistance(): 위의 두 함수를 차례로 호출하여 전체 최소 거리를 계산하고 반환하는 핵심 로직입니다.
참고: 초기값으로 INT8_MAX 대신 <climits> 헤더의 INT_MAX를 사용하는 것이 더 일반적이고 안전합니다. 시간 복잡도는 트리의 모든 노드를 최대 한 번씩 방문하므로 O(n)입니다.
실행 결과
Closest distance of leaf from -5 is: 1