C++에서 하위 트리도 BST가 되도록 이진 트리의 최대 하위 트리 합계

<시간/>

이 자습서에서는 하위 트리도 BST가 되도록 이진 트리에서 최대 하위 트리 합계를 찾는 프로그램에 대해 설명합니다.

이를 위해 이진 트리가 제공됩니다. 우리의 임무는 이진 검색 트리이기도 한 하위 트리의 합계를 출력하는 것입니다.

예시

#include <bits/stdc++.h>
using namespace std;
//creating binary tree node
struct Node {
   struct Node* left; struct Node* right; int data;
   Node(int data) {
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
struct Info {
   int max;
   int min;
   bool isBST;
   int sum;
   int currmax;
};
Info MaxSumBSTUtil(struct Node* root, int& maxsum) {
   if (root == NULL) return { INT_MIN, INT_MAX, true, 0, 0 };
   if (root->left == NULL && root->right == NULL) {
      maxsum = max(maxsum, root->data);
      return { root->data, root->data, true, root->data, maxsum };
   }
   Info L = MaxSumBSTUtil(root->left, maxsum);
   Info R = MaxSumBSTUtil(root->right, maxsum);
   Info BST;
   if (L.isBST && R.isBST && L.max < root->data && R.min > root->data) {
      BST.max = max(root->data, max(L.max, R.max));
      BST.min = min(root->data, min(L.min, R.min));
      maxsum = max(maxsum, R.sum + root->data + L.sum);
      BST.sum = R.sum + root->data + L.sum;
      BST.currmax = maxsum;
      BST.isBST = true;
      return BST;
   }
   BST.isBST = false;
   BST.currmax = maxsum;
   BST.sum = R.sum + root->data + L.sum;
   return BST;
}
int MaxSumBST(struct Node* root) {
   int maxsum = INT_MIN;
   return MaxSumBSTUtil(root, maxsum).currmax;
}
int main() {
   struct Node* root = new Node(5);
   root->left = new Node(14);
   root->right = new Node(3);
   root->left->left = new Node(6);
   root->right->right = new Node(7);
   root->left->left->left = new Node(9);
   root->left->left->right = new Node(1);
   cout << MaxSumBST(root);
   return 0;
}