양의 정수 L이 있다고 가정해 보겠습니다. L은 포화 이진 트리(perfect binary tree)의 레벨 수를 나타냅니다. 이 트리의 리프 노드는 1부터 n까지 차례대로 번호가 매겨져 있으며, 여기서 n은 리프 노드의 총개수입니다. 또한 각 부모 노드의 값은 두 자식 노드 값의 합이 됩니다. 우리가 작성해야 할 프로그램은 이 포화 이진 트리에 있는 모든 노드 값의 총합을 출력하는 것입니다.
예를 들어 트리가 다음과 같다면 −
모든 노드의 총합은 30이 됩니다.
핵심 아이디어
트리를 자세히 살펴보면 결국 전체 노드의 합을 구하는 문제임을 알 수 있습니다. 리프 노드에는 1부터 n까지의 값이 순서대로 저장되어 있으므로, 등차수열 합 공식 n(n+1)/2를 이용해 리프 노드의 합을 손쉽게 구할 수 있습니다.
여기서 중요한 성질은, 부모 노드가 자식 노드들의 합이기 때문에 포화 이진 트리에서는 모든 레벨의 노드 합이 서로 동일하다는 점입니다. 따라서 마지막 레벨(리프 노드)의 합을 구한 뒤 레벨 수를 곱해주면, 트리를 일일이 순회하지 않고도 전체 노드의 합을 바로 계산할 수 있습니다.
알고리즘 단계
- 마지막 레벨의 리프 노드 개수를 구합니다: n = 2^(L−1)
- 공식 n(n+1)/2를 이용해 리프 노드의 합을 계산합니다.
- 리프 노드의 합에 레벨 수 L을 곱하여 전체 노드의 합을 구합니다.
예제 코드 (C++)
#include<iostream>
#include<cmath>
using namespace std;
int treeSum(int level) {
int total_leaves = pow(2, level - 1); // 마지막 레벨의 리프 노드 개수
int leaf_sum = (total_leaves * (total_leaves + 1)) / 2; // 리프 노드의 합
int sum = leaf_sum * level; // 각 레벨의 합이 같으므로 레벨 수를 곱함
return sum;
}
int main() {
int levels = 4;
cout << "Sum of all nodes for a perfect binary tree with level " << levels << " is: " << treeSum(levels);
}출력 결과
Sum of all nodes for a perfect binary tree with level 4 is: 144
레벨이 4인 경우를 살펴보면, 리프 노드는 2³ = 8개이고 리프 노드의 합은 8×9/2 = 36입니다. 각 레벨의 합이 모두 36으로 동일하므로, 전체 합은 36×4 = 144가 됩니다.
복잡도 분석
이 방법은 반복문 없이 수학 공식만 사용하므로 시간 복잡도는 O(1), 공간 복잡도 역시 O(1)입니다. 트리를 실제로 생성하거나 순회하지 않고도 입력된 레벨 수만으로 즉시 답을 구할 수 있다는 것이 이 접근 방식의 가장 큰 장점입니다.