aboutsummaryrefslogtreecommitdiff
path: root/max_product_split_bt.cpp
blob: 71fc9a4a3c0c52f7884caa33e2db768d07636c95 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "leetcode.h"

class Solution {
public:
  int maxProduct(TreeNode *root) {
    tot = solve(root), solve(root);
    return ans % (1e9 + 7);
  }

private:
  long ans = 0, tot = 0, sub;
  int solve(TreeNode *root) {
    if (!root)
      return 0;
    sub = root->val + solve(root->left) + solve(root->right);
    ans = max(ans, sub * (tot - sub));
    return sub;
  }
};