Maximum Sum BST in Binary Tree LeetCode solution in C++

1
class Solution {
2
 public:
3
  int ans = 0;
4

5
  array<int, 4> solve(TreeNode *root) {
6
    if (!root) return {1, 0, INT_MIN, INT_MAX};
7

8
    array<int, 4> l = solve(root->left);
9
    array<int, 4> r = solve(root->right);
10

11
    if (l[0] and r[0]) {
12
      if (root->val > l[2] and root->val < r[3]) {
13
        ans = max({ans, l[1], r[1]});
14
        return {1, l[1] + r[1] + root->val, max({root->val, l[2], r[2]}),
15
                min({root->val, l[3], r[3]})};
16
      }
17
    }
18

19
    return {0, max(l[1], r[1]), INT_MIN, INT_MAX};
20
  }
21

22
  int maxSumBST(TreeNode *root) {
23
    auto arr = solve(root);
24
    return max(ans, arr[1]);
25
  }
26
};