Tổng xoắn ốc tối đa trong cây nhị phân C++

Trong bài toán này, cho một cây nhị phân. Nhiệm vụ là tìm tổng xoắn ốc (spiral sum) lớn nhất trong cây nhị phân.

Khái niệm

Spiral sum là tổng các nút được duyệt theo thứ tự xoắn ốc: cấp 1 trái→phải, cấp 2 phải→trái, cấp 3 trái→phải,...

Tuy nhiên, bài toán yêu cầu tổng xoắn ốc tối đa - tức là dừng lại ở cấp nào đó để tổng lớn nhất, không nhất thiết duyệt hết cây.

Ví dụ minh họa

Output: 6

Giải thích: Duyệt xoắn ốc: cấp 1: 1; cấp 2: 5, -1; cấp 3: -4, 6, -9, 1. Tổng tích lũy: 1 → 6 → 5 → -1. Giá trị lớn nhất là 6 (tại cấp 2).

Chương trình tìm tổng xoắn ốc tối đa

#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;
}

// Tìm tổng lớn nhất của dãy con liên tiếp (Kadane's algorithm)
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; // Right to Left
    stack<Node*> sLtR; // Left to Right
    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;
}

Kết quả

Maximum Spiral Sum in binary tree : 6

Giải thích thuật toán: Sử dụng 2 stack để duyệt xoắn ốc, lưu các giá trị vào vector. Sau đó áp dụng thuật toán Kadane để tìm tổng lớn nhất của dãy con liên tiếp trong vector đó.