문제 개요
이 문제에서는 하나의 트리를 나타내는 크기 n의 배열 arr[]가 주어집니다. 우리의 과제는 부모 배열(parent array)로 표현된 이진 트리의 높이를 구하는 것입니다.
부모 배열 표현이란 각 인덱스 i에 대해 arr[i]가 i번째 노드의 부모 노드 인덱스를 의미하는 방식입니다. 루트 노드는 부모가 없으므로 그 값은 -1로 표시됩니다.
트리의 높이(height)란 루트 노드에서 가장 먼 리프(leaf) 노드까지 이동할 때 거치게 되는 노드의 수를 말합니다.
해결 접근 방법
방법 1: 트리를 직접 생성하기
가장 단순한 해결책은 부모 배열로부터 실제 트리를 구성하는 것입니다. 트리의 루트를 찾은 뒤 해당 인덱스를 기준으로 재귀 호출을 통해 왼쪽과 오른쪽 서브트리를 만들고, 그 과정에서 얻어지는 최대 높이를 반환하면 됩니다.
방법 2: 깊이 배열 활용하기 (더 효율적)
보다 효율적인 방법은 배열에서 각 노드의 깊이(depth)를 계산해 별도의 깊이 배열에 저장한 후, 그중 최댓값을 반환하는 것입니다. 각 노드의 깊이는 '부모 노드의 깊이 + 1'이라는 관계로 정의되며, 이미 계산된 깊이는 다시 구하지 않는 메모이제이션 기법을 사용하면 모든 노드의 깊이를 한 번씩만 계산하게 되어 전체 시간 복잡도가 O(n)이 됩니다.
솔루션 동작을 보여주는 프로그램
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 노드 i의 깊이를 재귀적으로 계산
void findAllDepths(int arr[], int i, int nodeDepth[]) {
// 이미 깊이가 계산된 노드라면 종료
if (nodeDepth[i])
return;
// 부모가 없으면 루트 노드 → 깊이 1
if (arr[i] == -1) {
nodeDepth[i] = 1;
return;
}
// 부모 노드의 깊이가 아직 계산되지 않았다면 재귀 호출
if (nodeDepth[arr[i]] == 0)
findAllDepths(arr, arr[i], nodeDepth);
// 현재 노드의 깊이 = 부모 노드의 깊이 + 1
nodeDepth[i] = nodeDepth[arr[i]] + 1;
}
// 이진 트리의 최대 높이 계산
int findMaxHeightBT(int arr[], int n) {
int nodeDepth[n];
for (int i = 0; i < n; i++)
nodeDepth[i] = 0;
// 모든 노드의 깊이 계산
for (int i = 0; i < n; i++)
findAllDepths(arr, i, nodeDepth);
// 최대 깊이(= 트리의 높이) 탐색
int maxHeight = nodeDepth[0];
for (int i = 1; i < n; i++)
if (maxHeight < nodeDepth[i])
maxHeight = nodeDepth[i];
return maxHeight;
}
int main() {
int arr[] = {-1, 0, 0, 1, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum height of binary Tree is "<<findMaxHeightBT(arr, n);
return 0;
}
출력 결과
The maximum height of binary Tree is 3
동작 원리 설명
예제 입력 {-1, 0, 0, 1, 1}의 경우 트리 구조는 다음과 같습니다.
- 노드 0: 부모가 없으므로(-1) 루트 노드이며, 깊이는 1
- 노드 1, 2: 부모가 0이므로 깊이는 2
- 노드 3, 4: 부모가 1이므로 깊이는 3
가장 깊은 노드의 깊이가 3이므로, 트리의 최대 높이는 3이 됩니다.
복잡도 분석
시간 복잡도: O(n) — 메모이제이션 덕분에 각 노드의 깊이는 정확히 한 번만 계산됩니다.
공간 복잡도: O(n) — 깊이를 저장하는 배열과 재귀 호출 스택이 추가로 필요합니다.