C++のバイナリツリーの最大スパイラル合計

二分木で最大スパイラル和を見つけるプログラム

#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