hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Maximum Product of Splitted Binary Tree
Problem: 1339. Maximum Product of Splitted Binary Tree
Problem Link: https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/
Approach:
The first step is to traverse the binary tree, to sum up, all the node values.
Then traverse the tree again and subtract the sum of any sub-tree sum (left sub-tree sum + right sub-tree sum + current node's sum).
So, left_sum = total - current sub-tree sum.
Now multiply left_sum with the current sub-tree sum.
Take the maximum among the multiplied values.
Return the maximum modulo 109 + 7.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(1) + Auxilary Recursive Stack
Code [C++]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
const int MOD = 1e9 + 7;
long long maxVal = 0, total;
bool type = 0;
long long solve(TreeNode * root){
if(!root) return 0;
long long left = solve(root->left);
long long right = solve(root->right);
if(type){
maxVal = max(maxVal, left * (total - left));
maxVal = max(maxVal, right * (total - right));
long long newSum =(left + right + root->val);
maxVal = max(maxVal, newSum * (total - newSum));
}
return (left + right + root->val);
}
int maxProduct(TreeNode* root) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
total = solve(root); type = true;
solve(root);
return maxVal % MOD;
}
};