C++ 이진 트리에서 최대 레벨 합 구하는 방법

문제 개요

이번 문제에서는 양수와 음수 값을 모두 포함하는 이진 트리(Binary Tree)가 주어집니다. 우리의 목표는 각 레벨별 노드 값의 합을 계산하고, 그중 가장 큰 값을 찾는 것입니다.

문제 설명

주어진 이진 트리에서 각 레벨(level)에 속한 노드 값들을 모두 더한 뒤, 그 합들 중 최댓값을 반환하면 됩니다.

예시로 이해하기

C++ 이진 트리에서 최대 레벨 합 구하는 방법

출력: 5

설명:

레벨 1의 합: 3
레벨 2의 합: -3 + 4 = 1
레벨 3의 합: 5 - 1 + 6 - 5 = 5

따라서 최대 레벨 합은 5가 됩니다.

해결 접근 방법

이 문제는 레벨 순서 순회(Level Order Traversal), 즉 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

큐(queue)를 사용해 트리를 레벨 단위로 탐색합니다.
각 레벨을 처리할 때 해당 레벨에 있는 노드 값들의 합(levelSum)을 계산합니다.
매 레벨마다 현재까지의 최댓값(maxSum)과 비교하여 더 큰 값으로 갱신합니다.
모든 레벨의 탐색이 끝나면 maxSum을 반환합니다.

큐에 들어있는 노드 수를 미리 확인하면 한 번의 반복으로 정확히 하나의 레벨만 처리할 수 있어, 레벨별 합계를 깔끔하게 구할 수 있다는 점이 이 방식의 장점입니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* newNode(int data){
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

int findMaxLevelSum(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();
            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;
}

int main(){
    struct Node* root = newNode(3);
    root->left = newNode(-3);
    root->right = newNode(4);
    root->left->left = newNode(5);
    root->left->right = newNode(-1);
    root->right->left = newNode(6);
    root->right->right = newNode(-5);
    cout<<"최대 레벨 합은 "<<findMaxLevelSum(root);
    return 0;
}

실행 결과

최대 레벨 합은 5

복잡도 분석

이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(N)입니다. 여기서 N은 노드의 총 개수입니다. 공간 복잡도 역시 큐에 저장되는 노드 수가 최악의 경우 트리의 마지막 레벨 전체가 될 수 있으므로 O(W)(W는 트리의 최대 폭)이며, 일반적으로 O(N)으로 표현합니다.