문제 개요
이 문제에서는 하나의 이진 트리, 목표 노드(target node), 그리고 정수 K가 주어집니다. 목표 노드로부터 거리가 정확히 K만큼 떨어져 있는 트리 내의 모든 노드를 찾아 출력하는 것이 과제입니다.
이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드(없음·하나·둘)를 가질 수 있는 특수한 형태의 트리 자료구조입니다.
예제로 이해하기
다음 예제를 통해 문제를 살펴보겠습니다.
- K = 2
- 목표 노드: 9
- 출력 결과: 5 1 3
설명 − 거리는 목표 노드보다 위쪽(조상 방향), 아래쪽(자손 방향), 또는 같은 레벨의 노드까지 측정될 수 있습니다. 따라서 각 경우에 맞게 노드를 찾아 반환해야 합니다.
접근 방법
이 문제를 해결하려면 먼저 목표 노드에서 거리 K만큼 떨어져 있는 노드들이 어떤 유형인지 이해해야 합니다.
위 예제에서 확인할 수 있듯이, 거리 K에 있는 노드는 크게 두 가지 위치에 존재할 수 있습니다.
- 목표 노드의 서브트리 내부 — 예: 노드 5와 1
- 목표 노드의 조상 노드를 통과하는 반대편 서브트리 — 예: 노드 3
첫 번째 경우: 목표 노드의 서브트리 탐색
첫 번째 경우는 목표 노드의 서브트리를 재귀적으로 순회하면서 각 노드가 목표 노드로부터 거리 K인지 확인하면 됩니다. 조건을 만족하는 노드를 발견하면 출력합니다.
두 번째 경우: 조상 노드 활용
두 번째 경우는 목표 노드의 조상 노드들을 거슬러 올라가면서, 각 조상의 반대편 서브트리에서 목표 노드로부터 거리 K에 해당하는 노드들을 찾아 출력해야 합니다.
C++ 구현 코드
아래 프로그램은 위에서 설명한 해결 방법의 전체 구현을 보여줍니다.
#include <iostream>
using namespace std;
struct node {
int data;
struct node *left, *right;
};
void printSubtreeNodes(node *root, int k) {
if (root == NULL || k < 0) return;
if (k == 0) {
cout << root->data << "\t";
return;
}
printSubtreeNodes(root->left, k - 1);
printSubtreeNodes(root->right, k - 1);
}
int printKNodes(node* root, node* target, int k) {
if (root == NULL) return -1;
if (root == target) {
printSubtreeNodes(root, k);
return 0;
}
int dl = printKNodes(root->left, target, k);
if (dl != -1) {
if (dl + 1 == k)
cout << root->data << "\t";
else
printSubtreeNodes(root->right, k - dl - 2);
return 1 + dl;
}
int dr = printKNodes(root->right, target, k);
if (dr != -1) {
if (dr + 1 == k)
cout << root->data << endl;
else
printSubtreeNodes(root->left, k - dr - 2);
return 1 + dr;
}
return -1;
}
node *insertNode(int data) {
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main() {
node *root = insertNode(6);
root->left = insertNode(3);
root->right = insertNode(9);
root->left->right = insertNode(4);
root->right->left = insertNode(8);
root->right->right = insertNode(10);
root->right->right->left = insertNode(5);
root->right->right->right = insertNode(1);
node *target = root->right;
int K = 2;
cout << "Nodes at distance " << K << " from the target node are :\n";
printKNodes(root, target, K);
return 0;
}
실행 결과
Nodes at distance 2 from the target node are − 5 1 3
복잡도 분석
시간 복잡도: O(n) — 트리의 모든 노드를 최대 한 번씩 방문합니다.
공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이(h)에 비례합니다.
마무리
이 알고리즘은 목표 노드를 기준으로 아래쪽 서브트리와 위쪽 조상 경로를 나누어 처리함으로써, 트리 내 어느 위치에 있든 거리 K에 있는 모든 노드를 효율적으로 찾아낼 수 있습니다.