이 문제에서는 하나의 이진 트리(binary tree)가 주어집니다. 우리가 작성해야 할 프로그램은 주어진 이진 트리의 모든 레벨(level) 중에서 잎이 아닌 노드(non-leaf node)들의 합이 가장 큰 값을 찾아 출력하는 것입니다.
문제 설명
트리의 각 레벨별로 잎이 아닌 노드들의 데이터 합을 계산한 뒤, 그 값들 중 최대값을 구해 출력합니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력 −
출력 − 9
설명 − 각 레벨별 잎이 아닌 노드의 합은 다음과 같습니다.
레벨 1: 4 레벨 2: 1 + 2 = 3 레벨 3: 9 (4, 7은 잎 노드이므로 제외) 레벨 4: 0
접근 방식
이 문제를 해결하려면 이진 트리를 레벨 순서 순회(level order traversal, BFS) 방식으로 탐색하면서, 각 레벨에 속한 노드들 중 잎이 아닌 노드들의 합을 구한 후 그중 최대값을 찾으면 됩니다.
구체적인 동작 과정은 다음과 같습니다.
- 큐(queue)를 사용해 트리를 레벨 단위로 순회합니다.
- 각 레벨에서 현재 노드에 왼쪽 또는 오른쪽 자식이 존재하는지 확인합니다. 자식이 있다면, 즉 그 노드가 잎 노드가 아니라면 해당 노드의 값을 레벨 합(levelSum)에 더합니다.
- 자식 노드가 있는 경우에는 그 자식들을 큐에 삽입하여 다음 레벨 탐색 대상으로 만듭니다.
- 한 레벨의 순회가 끝나면 해당 레벨의 합과 지금까지의 최대합(maxSum)을 비교해, 더 큰 값으로 maxSum을 갱신합니다.
- 모든 레벨의 탐색이 끝나면 maxSum을 결과로 반환합니다.
예제 코드
위 접근 방식을 구현한 C++ 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
int maxLevelSum(struct Node* root){
if (root == NULL)
return 0;
int maxSum = root->data;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int count = q.size();
int levelSum = 0;
while (count--) {
Node* temp = q.front();
q.pop();
if (temp->left != NULL || temp->right != NULL)
levelSum = levelSum + temp->data;
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
maxSum = max(levelSum, maxSum);
}
return maxSum;
}
struct Node* insertNode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main() {
struct Node* root = insertNode(6);
root->left = insertNode(1);
root->right = insertNode(2);
root->left->left = insertNode(4);
root->left->right = insertNode(7);
root->right->right = insertNode(9);
root->right->right->left = insertNode(5);
cout<<"이진 트리의 한 레벨에서 잎이 아닌 노드들의 최대 합은 "<<maxLevelSum(root);
return 0;
}
출력 결과
이진 트리의 한 레벨에서 잎이 아닌 노드들의 최대 합은 9
복잡도 분석
시간 복잡도: O(N) — 트리의 모든 노드를 정확히 한 번씩 방문합니다. 여기서 N은 트리의 전체 노드 수입니다.
공간 복잡도: O(W) — 큐에는 한 레벨의 노드들이 저장되며, W는 트리의 최대 너비(가장 많은 노드를 가진 레벨의 노드 수)입니다.