C++ 이진 트리의 최대 나선 합

이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 C++의 이진 트리에서 최대 나선 합을 찾는 프로그램을 만드는 것입니다.

나선 합계 이진 트리의 나선형 순회에서 만나는 노드의 합은 이진 트리의 합입니다.

트리의 나선형 순회에서 노드는 루트에서 리프 노드로 순회됩니다. 순회는 왼쪽에서 오른쪽으로, 다음 레벨에서는 오른쪽에서 왼쪽으로, 다음 레벨에서는 계속 진행됩니다.

예 -

출력 -5

설명 -

트리의 두 번째 수준의 첫 번째 노드까지 나선형 탐색을 고려할 것입니다.

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