이 문제에서는 하나의 이진 트리가 주어지며, 우리의 목표는 이진 트리의 최소 깊이(Minimum Depth)를 구하는 것입니다.
이진 트리는 각 노드가 최대 두 개의 자식 노드만 가질 수 있다는 특수한 조건을 지닌 트리 구조입니다.
여기서 말하는 최소 깊이란 루트 노드에서 임의의 리프 노드까지 이르는 가장 짧은 경로의 길이를 의미합니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력
출력
2
위 트리에서 루트 노드 5의 오른쪽 자식인 노드 9가 바로 리프 노드이므로, 루트에서 리프까지의 경로 길이는 2가 됩니다.
접근 방법 1: 재귀적 순회
가장 기본적인 해결 방법은 이진 트리를 순회하면서 각 노드의 높이를 계산하는 것입니다. 각 비단말(non-leaf) 노드에 대해 자식 노드를 재귀적으로 호출하고, 리프 노드에 도달하면 1을 반환합니다.
이때 한쪽 자식만 존재하는 노드는 주의가 필요합니다. 존재하지 않는 자식의 깊이가 0으로 계산되어 잘못된 최솟값이 반환될 수 있으므로, 자식이 하나뿐인 경우에는 해당 자식의 깊이를 그대로 사용해야 합니다.
해결 방법의 동작을 보여주는 프로그램입니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
int findMinDepthBT(Node *currentNode) {
if (currentNode == NULL)
return 0;
if (currentNode->left == NULL && currentNode->right == NULL)
return 1;
if (!currentNode->left)
return findMinDepthBT(currentNode->right) + 1;
if (!currentNode->right)
return findMinDepthBT(currentNode->left) + 1;
return min(findMinDepthBT(currentNode->left),
findMinDepthBT(currentNode->right)) + 1;
}
Node *newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int main() {
Node *root = newNode(5);
root->left = newNode(2);
root->right = newNode(9);
root->left->left = newNode(5);
root->left->right = newNode(1);
root->left->left->left = newNode(7);
root->left->left->right = newNode(3);
cout << "The minimum depth of binary tree is " << findMinDepthBT(root);
return 0;
}
출력
The minimum depth of binary tree is 2
이 접근 방식은 상당히 효율적이지만, 다른 순회 기법을 활용하면 최소 깊이를 더 효과적으로 찾을 수 있습니다.
접근 방법 2: 레벨 순서 순회(BFS)
대표적인 대안은 레벨 순서 순회(level order traversal)입니다. 이 방법은 큐(queue)를 사용해 트리를 레벨 단위로 탐색하며, 처음으로 리프 노드를 만난 시점의 레벨 번호를 곧바로 반환합니다.
전체 트리를 끝까지 탐색하기 전에 답을 얻을 수 있으므로, 최소 깊이가 얕은 트리에서는 재귀 방식보다 빠르게 종료될 수 있다는 장점이 있습니다.
해결 방법의 동작을 보여주는 프로그램입니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct lOrderQueue {
Node *node;
int depth;
};
int findMinDepthBT(Node *root) {
if (root == NULL)
return 0;
queue<lOrderQueue> levelOrder;
lOrderQueue deQueue = {root, 1};
levelOrder.push(deQueue);
while (levelOrder.empty() == false) {
deQueue = levelOrder.front();
levelOrder.pop();
Node *node = deQueue.node;
int depth = deQueue.depth;
if (node->left == NULL && node->right == NULL)
return depth;
if (node->left != NULL) {
deQueue.node = node->left;
deQueue.depth = depth + 1;
levelOrder.push(deQueue);
}
if (node->right != NULL) {
deQueue.node = node->right;
deQueue.depth = depth + 1;
levelOrder.push(deQueue);
}
}
return 0;
}
Node* newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main() {
Node *root = newNode(5);
root->left = newNode(2);
root->right = newNode(9);
root->left->left = newNode(5);
root->left->right = newNode(1);
root->left->left->left = newNode(7);
root->left->left->right = newNode(3);
cout << "The minimum depth of binary tree is " << findMinDepthBT(root);
return 0;
}
출력
The minimum depth of binary tree is 2
두 방법 모두 최악의 경우 시간 복잡도는 O(n)으로 동일하지만, BFS 방식은 첫 번째 리프 노드를 만나면 즉시 탐색을 중단할 수 있어 실제 실행 시간을 단축할 수 있습니다. 따라서 트리의 형태에 따라 적절한 방법을 선택하는 것이 좋습니다.