C++で二分木の最大スパイラル和を求める方法

この記事では、二分木が与えられたときに、その最大スパイラル和（Maximum Spiral Sum）を求めるプログラムをC++で作成します。

スパイラル和とは？

スパイラル和とは、二分木をスパイラル（ジグザグ）順に走査したときに通るノードの値の合計のことです。

スパイラル走査では、ノードを根（ルート）から葉に向かって辿ります。第1レベルは左から右へ、次のレベルは右から左へ、さらにその次はまた左から右へと、レベルごとに走査方向を交互に切り替えながら進むのが特徴です。

問題の例

例として、次のような二分木を考えてみましょう。

            1
          /   \
         5    -1
        / \   /  \
      -4   6 -9    1

この木をスパイラル順に走査すると、ノードの並びは「1 → 5 → -1 → 1 → -9 → 6 → -4」となります。

この並びの中から連続する部分列の合計が最大になるものを探すと、「1 + 5 = 6」が最大となります。レベルの後半には負の値（-9 や -4）が含まれているため、そこまで含めてしまうと合計が減少し、最大和になりません。

したがって、この二分木の最大スパイラル和は 6 です。

アルゴリズムの考え方

この問題は、次の手順で解くことができます。

1. 2つのスタックを交互に使用して二分木をスパイラル順に走査し、訪問したノードの値を配列に格納します。
2. 得られた配列に対して、カダネのアルゴリズム（Kadane's Algorithm／最大部分配列和を求める手法）を適用します。
3. その結果が、二分木の最大スパイラル和となります。

2つのスタックを使い分けることで、レベルごとに走査方向を反転させるスパイラル走査を効率的に実現できます。また、負の値が含まれる場合でも、カダネのアルゴリズムにより合計が最大となる連続区間だけを正確に抽出できます。

C++での実装例

以下が、二分木の最大スパイラル和を求めるC++プログラムです。

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

// 二分木のノード構造体
class Node {
public:
    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) ― 各ノードをちょうど1回ずつ訪問し、その後カダネのアルゴリズムを線形時間で実行します。
空間計算量：O(n) ― 走査に使用する2つのスタックと、ノード値を格納する配列が必要になります。

このように、スパイラル走査とカダネのアルゴリズムを組み合わせることで、負のノード値が含まれる二分木でも最大スパイラル和を効率的に求めることができます。