ผลรวมเกลียวสูงสุดใน Binary Tree ใน C++

ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือสร้างโปรแกรมที่จะหาผลรวมเกลียวสูงสุดในไบนารีทรีใน C++

ผลรวมเกลียว ของไบนารีทรีคือผลรวมของโหนดที่พบในการเคลื่อนที่แบบเกลียวของไบนารีทรี

ในการเคลื่อนที่แบบเกลียวของต้นไม้ โหนดจะเคลื่อนที่จากรากไปยังโหนดใบ การข้ามผ่านจะเกิดขึ้นจากซ้ายไปขวา จากนั้นสำหรับระดับถัดไปจากขวาไปซ้าย และต่อไปสำหรับระดับต่อไป

ตัวอย่าง −

ผลผลิต −5

คำอธิบาย −

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

1+ 5 = 5.

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

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

ตัวอย่าง

โปรแกรมหาผลรวมก้นหอยสูงสุดในไบนารีทรี

#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