이 문제에서는 하나의 이진 트리(binary tree)와 숫자 K가 주어지며, 리프 노드로부터 거리가 k만큼 떨어진 트리의 모든 노드를 출력해야 합니다.
핵심 개념 정리
이진 트리(Binary Tree)란 각 노드가 최대 두 개의 자식 노드(0개, 1개 또는 2개)를 가질 수 있는 특수한 형태의 트리 자료구조입니다.
리프 노드(Leaf Node)는 이진 트리에서 가장 끝에 위치한, 즉 자식 노드가 없는 노드를 의미합니다.
이 문제에서 '리프 노드로부터의 거리'는 해당 노드가 리프 노드보다 몇 단계 위의 레벨에 있는지를 나타냅니다. 예를 들어, 레벨 4에 있는 리프 노드로부터 거리가 2인 노드는 레벨 2에 존재하게 됩니다.
문제 이해를 위한 예시
K = 2일 때,
출력 결과 − 6 9
문제 해결 접근 방법
이 문제를 해결하기 위해 트리를 순회(traversal)하면서, 리프 노드에 도달할 때까지 각 레벨별로 부모 노드들의 집합(조상 노드, ancestor nodes)을 저장합니다. 그런 다음 리프 노드로부터 거리가 k만큼 떨어진 조상 노드를 출력하면 됩니다.
순회 과정에서 이미 방문한 노드를 표시하는 것이 매우 중요합니다. 이를 통해 동일한 노드가 중복으로 출력되는 것을 방지할 수 있으며, 여기서는 불리언(boolean) 배열을 활용하여 방문 여부를 관리합니다.
이 알고리즘은 오직 트리 순회만을 사용하므로, 수행 시간은 노드의 개수 n에 비례합니다.
시간 복잡도: O(n)
예제 코드
위에서 설명한 로직을 구현한 프로그램은 다음과 같습니다 −
#include <iostream>
using namespace std;
#define MAX_HEIGHT 10000
struct Node {
int key;
Node *left, *right;
};
Node* insertNode(int key){
Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return (node);
}
void nodesKatDistance(Node* node, int path[], bool visited[], int pathLen, int k){
if (node==NULL) return;
path[pathLen] = node->key;
visited[pathLen] = false;
pathLen++;
if (node->left == NULL && node->right == NULL && pathLen-k-1 >= 0 && visited[pathLen-k-1] == false){
cout<<path[pathLen-k-1]<<"\t";
visited[pathLen-k-1] = true;
return;
}
nodesKatDistance(node->left, path, visited, pathLen, k);
nodesKatDistance(node->right, path, visited, pathLen, k);
}
void printNodes(Node* node, int k){
int path[MAX_HEIGHT];
bool visited[MAX_HEIGHT] = {false};
nodesKatDistance(node, path, visited, 0, k);
}
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->left->left = insertNode(5);
root->right->left->right = insertNode(1);
int k = 2;
cout<<"All nodes at distance "<<k<<" from leaf node are:\n";
printNodes(root, k);
return 0;
}
실행 결과
리프 노드로부터 거리가 2만큼 떨어진 모든 노드는 다음과 같습니다 −
6 9