C++로 이진 트리에서 최대 서브트리 합 구하기

문제 소개

이 문제에서는 하나의 이진 트리(binary tree)가 주어지며, 우리의 목표는 트리 전체에서 노드 값의 합이 가장 큰 서브트리(subtree)를 찾는 것입니다.

문제 설명: 주어진 이진 트리에는 양수와 음수가 함께 존재합니다. 따라서 단순히 루트부터 계산한 합만 고려해서는 안 되며, 트리 내 모든 서브트리 중에서 노드 값의 합이 최대가 되는 것을 찾아야 합니다.

예시를 통해 문제를 살펴보겠습니다.

출력: 13

설명:

왼쪽 서브트리의 합: 7
오른쪽 서브트리의 합: 1
전체 트리의 합: 13

위 예시에서 루트 노드를 포함한 전체 트리의 합이 13으로 가장 크므로 정답은 13이 됩니다.

해결 접근 방법

이 문제는 후위 순회(post-order traversal)를 이용하면 효율적으로 해결할 수 있습니다. 후위 순회란 왼쪽 자식 → 오른쪽 자식 → 현재 노드 순서로 방문하는 순회 방식입니다.

알고리즘의 동작 과정은 다음과 같습니다.

현재 노드의 왼쪽 서브트리 합과 오른쪽 서브트리 합을 재귀적으로 계산합니다.
현재 노드의 값에 두 서브트리의 합을 더해, 현재 노드를 루트로 하는 서브트리의 전체 합을 구합니다.
이 합이 지금까지 기록된 최댓값보다 크면 최댓값을 갱신합니다.
잎 노드(leaf)부터 루트까지 모든 노드에 대해 위 과정을 반복하면 최대 서브트리 합을 구할 수 있습니다.

이 방식은 각 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N)이며, 공간 복잡도는 재귀 호출 스택으로 인해 O(H)(H는 트리의 높이)입니다.

구현 예제

#include <iostream>
using namespace std;

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

Node* newNode(int key) {
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

// 후위 순회로 서브트리 합을 계산하고 최댓값을 갱신하는 함수
int calcSumTreeSumRec(Node* root, int& ans) {
    if (root == NULL)
        return 0;
    int currSum = root->key + calcSumTreeSumRec(root->left, ans) + calcSumTreeSumRec(root->right, ans);
    ans = max(ans, currSum);

    return currSum;
}

int calcMaxSubTreeSum(Node* root) {
    if (root == NULL)
        return 0;
    int ans = -100;
    calcSumTreeSumRec(root, ans);
    return ans;
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(-4);
    root->right = newNode(4);
    root->left->left = newNode(3);
    root->left->right = newNode(8);
    root->right->left = newNode(-5);
    root->right->right = newNode(2);

    cout << "The largest subtree sum is " << calcMaxSubTreeSum(root);
    return 0;
}

출력 결과

The largest subtree sum is 13

마무리

후위 순회와 재귀를 활용하면 트리의 모든 서브트리 합을 단 한 번의 순회로 계산하면서 동시에 최댓값을 추적할 수 있습니다. 음수 값이 포함된 트리에서도 정확하게 동작하며, 코드가 간결하여 코딩 테스트나 실무에서 트리 관련 문제를 해결할 때 유용하게 활용할 수 있는 패턴입니다.