비어 있지 않은 특수한 이진 트리가 있다고 가정해 봅시다. 이 트리의 각 노드는 음수가 아닌 값을 가지며, 자식 노드를 정확히 2개 또는 0개 가집니다. 만약 어떤 노드가 두 개의 자식을 가진다면, 그 노드의 값은 항상 두 자식 노드 값 중 더 작은 값입니다. 즉, root.val = min(root.left.val, root.right.val) 관계가 성립합니다.
이러한 이진 트리가 주어졌을 때, 트리 전체 노드 값들의 집합에서 두 번째 최솟값을 찾아야 합니다. 만약 두 번째 최솟값이 존재하지 않는다면 -1을 반환하면 됩니다.
예를 들어 다음과 같은 트리가 입력으로 주어진 경우를 살펴보겠습니다.
이 경우 출력 결과는 5입니다. 트리에서 가장 작은 값은 2이고, 두 번째로 작은 값은 5이기 때문입니다.
문제 해결 접근 방법
이 문제는 트리를 순회하면서 최솟값보다 큰 값들 중 가장 작은 값을 추적하는 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- TraverseNodes() 함수를 정의합니다. 이 함수는 node, min, nextMin 세 개의 매개변수를 받습니다.
- node가 null이라면 그대로 반환합니다.
- node의 값이 min보다 크다면:
- nextMin이 아직 -1(미발견 상태)이거나, node의 값이 현재 nextMin보다 작다면 nextMin을 node의 값으로 갱신합니다.
- 왼쪽 자식과 오른쪽 자식에 대해 재귀적으로 TraverseNodes()를 호출합니다.
- 메인 메서드에서는 다음을 수행합니다:
- root가 null이 아니면 min을 root의 값으로, null이면 -1로 설정합니다.
- nextMin을 -1로 초기화합니다.
- TraverseNodes(root, min, nextMin)을 호출한 뒤 nextMin을 반환합니다.
C++ 구현 코드
아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
int findSecondMinimumValue(TreeNode* root) {
int min = (root && root->val != 0) ? root->val : -1;
int nextMin = -1;
TraverseNodes(root, min, nextMin);
return nextMin;
}
void TraverseNodes(TreeNode* node, int min, int& nextMin) {
if (!node || node->val == 0) {
return;
}
if (node->val > min) {
if (nextMin == -1 || node->val < nextMin) {
nextMin = node->val;
}
}
TraverseNodes(node->left, min, nextMin);
TraverseNodes(node->right, min, nextMin);
}
};
main(){
Solution ob;
vector<int> v = {2,2,5,NULL,NULL,5,7};
TreeNode *root = make_tree(v);
cout << (ob.findSecondMinimumValue(root));
}입력
{2,2,5,NULL,NULL,5,7}출력
5
동작 원리 정리
이 알고리즘의 핵심은 트리의 특성을 활용하는 것입니다. 부모 노드의 값이 항상 자식 노드들의 최솟값과 같다는 규칙 때문에, 루트 노드의 값이 곧 전체 트리의 최솟값이 됩니다. 따라서 DFS(깊이 우선 탐색)로 트리를 순회하면서 루트 값보다 큰 노드들만 대상으로 삼아, 그중 가장 작은 값을 찾으면 됩니다.
시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)이며, 공간 복잡도는 재귀 호출 스택 깊이에 비례하여 최악의 경우 O(n)입니다.