C++ 이진 트리의 최대 나선 합(Spiral Sum) 구현 방법

문제 개요

하나의 이진 트리(binary tree)가 주어졌을 때, C++을 이용해 이 트리에서 얻을 수 있는 최대 나선 합(maximum spiral sum)을 찾는 프로그램을 작성하는 것이 이번 문제의 목표입니다.

여기서 나선 합(spiral sum)이란 이진 트리를 나선 방식으로 순회할 때 방문하게 되는 노드들의 값의 총합을 의미합니다.

나선(Spiral) 순회란?

나선 순회는 루트 노드에서 시작해 리프 노드 방향으로 내려가며 탐색합니다. 이때 한 레벨은 왼쪽에서 오른쪽으로, 다음 레벨은 오른쪽에서 왼쪽으로 방향을 번갈아 바꿔가며 진행되기 때문에 지그재그(zigzag) 형태의 레벨 순회라고도 할 수 있습니다.

예시

위 트리를 나선 방식으로 순회하면 노드는 다음 순서로 방문됩니다.

1 → 5 → -1 → -9 → 1 → -4 → 6

이 순서에서 최대 나선 합은 처음 두 노드까지만 더한 값입니다.

1 + 5 = 6

그다음 노드부터는 음수(-1, -9, -4 등)가 포함되어 누적 합을 오히려 감소시키므로, 최대 합을 구할 때는 해당 지점 이후의 나선 구간을 제외합니다.

접근 방법

이 문제는 두 가지 기법을 조합하면 효율적으로 해결할 수 있습니다.

1. 스택 두 개를 이용한 나선 순회: 방향을 교차하며 각 레벨의 노드를 탐색하고, 방문한 노드의 값을 배열에 순서대로 저장합니다.
2. 카데인(Kadane) 알고리즘: 나선 순서대로 저장된 배열에 대해 최대 연속 부분합을 선형 시간에 계산하여 최대 나선 합을 구합니다.

C++ 구현 예제

다음은 이진 트리의 최대 나선 합을 구하는 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *left, *right;
};
Node* insertNode(int data){
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
int findMaxSum(vector<int> arr, int n){
    int sum = INT_MIN;
    int maxSum = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (sum < 0)
            sum = arr[i];
        else
            sum += arr[i];
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}
int SpiralSum(Node* root){
    if (root == NULL)
        return 0;
    stack<Node*> sRtL;
    stack<Node*> sLtR;
    vector<int> arr;
    sRtL.push(root);
    while (!sRtL.empty() || !sLtR.empty()) {
        while (!sRtL.empty()) {
            Node* temp = sRtL.top();
            sRtL.pop();
            arr.push_back(temp->data);
            if (temp->right)
                sLtR.push(temp->right);
            if (temp->left)
                sLtR.push(temp->left);
        }
        while (!sLtR.empty()) {
            Node* temp = sLtR.top();
            sLtR.pop();
            arr.push_back(temp->data);
            if (temp->left)
                sRtL.push(temp->left);
            if (temp->right)
                sRtL.push(temp->right);
        }
    }
    return findMaxSum(arr, arr.size());
}
int main(){
    Node* root = insertNode(1);
    root->left = insertNode(5);
    root->right = insertNode(-1);
    root->left->left = insertNode(-4);
    root->left->right = insertNode(6);
    root->right->left = insertNode(-9);
    root->right->right = insertNode(1);
    cout << "Maximum Spiral Sum in binary tree : "<<SpiralSum(root);
    return 0;
}

실행 결과

Maximum Spiral Sum in binary tree : 6

복잡도 분석

• 시간 복잡도: O(n) — 모든 노드를 정확히 한 번씩 방문합니다.
• 공간 복잡도: O(n) — 스택과 배열에 노드 정보를 저장하기 위한 공간이 필요합니다.