트리가 주어졌을 때, 루트에서 리프까지 이어지는 경로 중 길이가 주어진 값 k보다 짧은 경로의 리프 노드를 제거하는 문제를 살펴보겠습니다.
문제 예시
입력 —
K = 4
출력 —
문제 분석
주어진 경로는 다음과 같습니다. 1. A -> B -> C -> E 길이 = 4 2. A -> B -> C -> F 길이 = 4 3. A -> B -> D 길이 = 3 4. A -> G -> H 길이 = 3 5. A -> B -> I 길이 = 3 경로 3, 4, 5의 길이는 3으로 주어진 k(=4)보다 짧으므로, 해당 경로의 리프 노드인 D, H, I를 제거합니다. 여기서 주목할 점은, H와 I가 제거된 후에는 G 역시 리프 노드가 되고 그 경로 길이는 2로 여전히 k보다 짧다는 것입니다. 따라서 G도 추가로 제거하며 프로그램이 종료됩니다.
접근 방법
이 문제는 후위 순회(Post-order Traversal)를 활용하여 해결할 수 있습니다. 후위 순회는 왼쪽 서브트리와 오른쪽 서브트리를 먼저 처리한 뒤 현재 노드를 처리하는 방식이기 때문에, 리프 노드부터 차례대로 검사하고 제거하는 데 적합합니다.
재귀 함수를 만들어 각 노드까지의 경로 길이를 추적하면서, 리프 노드에 도달했을 때 해당 경로의 길이가 k보다 짧다면 그 노드를 삭제합니다. 노드가 삭제되면 부모 노드 입장에서는 새로운 리프 노드가 생길 수 있으므로, 재귀 호출이 자연스럽게 이 연쇄적인 제거 과정을 처리해 줍니다.
C++ 구현 코드
#include<bits/stdc++.h>
using namespace std;
struct Node{ // 노드 구조체 정의
char data;
Node *left, *right;
};
Node *newNode(int data){ // 새 노드 생성
Node *node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
Node *trimmer(Node *root, int len, int k){
if (!root) // root가 NULL이면 반환
return NULL;
root -> left = trimmer(root -> left, len + 1, k); // 왼쪽 서브트리 순회
root -> right = trimmer(root -> right, len + 1, k); // 오른쪽 서브트리 순회
if (!root -> left && !root -> right && len < k){
delete root;
return NULL;
}
return root;
}
Node *trim(Node *root, int k){
return trimmer(root, 1, k);
}
void printInorder(Node *root){
if (root){
printInorder(root->left);
cout << root->data << " ";
printInorder(root->right);
}
}
int main(){
int k = 4;
Node *root = newNode('A');
root->left = newNode('B');
root->right = newNode('G');
root->left->left = newNode('C');
root->left->right = newNode('D');
root->left->left->left = newNode('E');
root->left->left->right = newNode('F');
root->right->left = newNode('H');
root->right->right = newNode('I');
printInorder(root);
cout << "\n";
root = trim(root, k);
printInorder(root);
return 0;
}실행 결과
E C F B D A H G I E C F B A
코드 상세 설명
핵심이 되는 함수는 trimmer()입니다. 이 재귀 함수는 트리를 순회하면서 현재 노드까지의 경로 길이(len)를 인자로 전달받아 유지합니다.
동작 흐름은 다음과 같습니다.
1. 현재 노드가 NULL이면 즉시 반환합니다.
2. 왼쪽과 오른쪽 서브트리를 각각 재귀적으로 순회하며 경로 길이를 1씩 증가시켜 전달합니다.
3. 자식 노드가 없는 리프 노드에 도달하면, 그때까지 누적된 경로 길이가 k보다 짧은지 확인합니다.
4. 조건을 만족하면 해당 노드를 delete로 메모리에서 해제하고 NULL을 반환하여 부모와의 연결을 끊습니다. 그렇지 않으면 노드를 그대로 유지합니다.
이러한 방식 덕분에 H, I가 제거된 후 G가 새로운 리프 노드가 되는 경우에도, 상위 재귀 호출 단계에서 자동으로 감지하여 연쇄적으로 제거할 수 있습니다.
마무리
이번 글에서는 재귀와 후위 순회를 활용하여 루트에서 리프까지의 경로 길이가 K 미만인 노드를 제거하는 문제를 해결했습니다. C++ 구현 코드와 함께 전체 접근 방식을 단계별로 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 튜토리얼이 여러분의 학습에 도움이 되기를 바랍니다.