ผลรวมเกลียวสูงสุดในต้นไม้ไบนารีใน C++

บทนำ

ในปัญหานี้ เราได้รับต้นไม้ไบนารี (Binary Tree) มา ภารกิจคือสร้างโปรแกรมที่หาผลรวมเกลียวสูงสุด (Maximum Spiral Sum) ในต้นไม้ไบนารีด้วย C++

ผลรวมเกลียว (Spiral Sum) ของต้นไม้ไบนารี คือผลรวมของโหนดที่พบในการเดินทางแบบเกลียว (Spiral Traversal) ของต้นไม้

ในการเดินทางแบบเกลียว โหนดจะถูกเดินทางจากรากไปยังโหนดใบ การเดินทางจะสลับทิศทาง: ระดับแรกจากซ้ายไปขวา ระดับถัดไปจากขวาไปซ้าย และสลับกันไปเรื่อยๆ

ตัวอย่าง

ผลลัพธ์ - 5

คำอธิบาย -

เราพิจารณาการเดินทางแบบเกลียวจนถึงโหนดแรกของระดับที่ 2 ของต้นไม้

1 + 5 = 5

ผลรวมองค์ประกอบของแถวที่สามคือ (1 - 9 + 6 - 4 = -6) ซึ่งจะลดผลรวมรวมลง จึงถูกตัดออกขณะพิจารณาผลรวมสูงสุด

เพื่อแก้ปัญหานี้ เราจะใช้อาร์เรย์ที่เก็บผลรวมขององค์ประกอบแต่ละระดับ และใช้สแต็ก 2 ตัวเพื่อหาผลรวมเกลียวที่แต่ละระดับ ท้ายสุดจะตรวจสอบว่าการรวมผลรวมหลังระดับนั้นเพิ่มผลรวมสูงสุดหรือไม่ ถ้าใช่จึงนำมารวม มิฉะนั้นตัดทิ้ง

ตัวอย่างโปรแกรม

#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

คำอธิบายเพิ่มเติม

อัลกอริทึมใช้ 2 Stack:

• sRtL (Right to Left): ใช้สำหรับระดับที่เดินจากขวาไปซ้าย
• sLtR (Left to Right): ใช้สำหรับระดับที่เดินจากซ้ายไปขวา

ข้อมูลจากการเดินทางแบบเกลียวถูกเก็บใน vector arr แล้วนำไปหาผลรวมต่อเนื่องสูงสุด (Maximum Subarray Sum) ด้วยอัลกอริทึม Kadane's Algorithm ในฟังก์ชัน findMaxSum()