Maximum Product of Splitted Binary Tree LeetCode solution in C++

1
class Solution {
2
 public:
3
  int mod = 1e9 + 7;
4
  unordered_map<TreeNode *, pair<long long int, long long int>> mp;
5
  long long int helper(TreeNode *root) {
6
    if (!root) return 0;
7
    long long int ls = 0, rs = 0;
8
    if (root->left) ls = helper(root->left);
9
    if (root->right) rs = helper(root->right);
10
    mp[root] = {ls, rs};
11
    return ls + rs + root->val;
12
  }
13
  long long int ans = 0;
14
  void helper2(TreeNode *root, long long int adon) {
15
    if (root == NULL) return;
16
    long long int x = root->val + adon;
17
    ans = max(ans,
18
              max((x + mp[root].first) * mp[root].second, (x + mp[root].second) * mp[root].first));
19
    helper2(root->left, x + mp[root].second);
20
    helper2(root->right, x + mp[root].first);
21
  }
22
  int maxProduct(TreeNode *root) {
23
    long long int x = helper(root);
24
    helper2(root, 0);
25
    return ans % mod;
26
  }
27
};