Given the root of a binary tree, split the binary tree into two subtrees by removing one edge such that the product of the sums of the subtrees is maximized.

Return the maximum product of the sums of the two subtrees. Since the answer may be too large, return it modulo 109 + 7.

Note that you need to maximize the answer before taking the mod and not after taking it.

&nbsp;
Example 1:

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)


Example 2:

Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90
Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [2, 5 * 104].
	1 &lt;= Node.val &lt;= 104


class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        def findTotalSum(node, totalSum):
            if node is None:
                return totalSum
            totalSum = findTotalSum(node.left,totalSum)
            totalSum += node.val
            totalSum = findTotalSum(node.right,totalSum)
            return totalSum
        
        def dfs(node,maxProd,totalSum):
            if node is None:
                return maxProd,0
            if not node.left and not node.right:
                return maxProd,node.val
            maxProd, lSum = dfs(node.left,maxProd,totalSum)
            maxProd, rSum = dfs(node.right,maxProd,totalSum)
            subTreeSum = lSum+rSum+node.val
            maxProd = max(maxProd,(totalSum-lSum)*lSum,(totalSum-rSum)*rSum,(totalSum-subTreeSum)*subTreeSum)
            return maxProd, subTreeSum
        
        totalSum = findTotalSum(root, 0)
        product,_ = dfs(root,1,totalSum)
        return product % (pow(10,9)+7)
class Solution {
    public void findMaxSum(TreeNode node,long sum[]){
        if(node==null) return ;

        findMaxSum(node.left,sum);
        findMaxSum(node.right,sum);

        sum[0]+=node.val;

    }

    public long findProd(TreeNode node,long sum[],long []max){
        if(node==null) return 0;

        long left=findProd(node.left, sum, max);
        long right=findProd(node.right,sum,max);

        long val=left+right+node.val;

        max[0]=Math.max(max[0],val*(sum[0]-val));

        return val;
    }
    public int maxProduct(TreeNode root) {

        long max[]=new long[1];
        long sum[]=new long[1];

        findMaxSum(root,sum);

       long n= findProd(root,sum,max);

        return (int)(max[0]%((int)1e9+7));
    }
}
class Solution {
public:
    int mod = 1e9+7;
    unordered_map<TreeNode*,pair<long long int,long long int>> mp;
    long long int helper(TreeNode* root){
        if(!root)
            return 0;
        long long int ls = 0,rs = 0;
        if(root->left)
            ls = helper(root->left);
        if(root->right)
            rs = helper(root->right);
        mp[root] = {ls,rs};
        return ls+rs+root->val;
    }
    long long int ans = 0;
    void helper2(TreeNode* root,long long int adon){
        if(root == NULL)
            return;
        long long int x = root->val + adon;
        ans = max(ans,max((x+mp[root].first)*mp[root].second,(x+mp[root].second)*mp[root].first));
        helper2(root->left,x+mp[root].second);
        helper2(root->right,x+mp[root].first);
    }
    int maxProduct(TreeNode* root) {
        long long int x = helper(root);
        helper2(root,0);
        return ans%mod;
    }
};
var maxProduct = function(root) {
    const lefteRightSumMap = new Map();
    
    function getLeftRightSumMap(node) {
        if (node === null)
            return 0;

        let leftSum = getLeftRightSumMap(node.left);
        let rightSum = getLeftRightSumMap(node.right);
        
        lefteRightSumMap.set(node, {leftSum, rightSum});
        
        return leftSum + rightSum + node.val;
    }
    
    getLeftRightSumMap(root);
    
    let maxProduct = -Infinity;

    function getMaxProductDFS(node, parentSum) {
        if (node === null) return;
        
        const {leftSum, rightSum} = lefteRightSumMap.get(node);
        
        // cut left edge
        maxProduct = Math.max(maxProduct, leftSum * (parentSum + node.val + rightSum));
        
        // cut right edge
        maxProduct = Math.max(maxProduct, rightSum * (parentSum + node.val + leftSum));

        getMaxProductDFS(node.left, parentSum + node.val + rightSum);
        getMaxProductDFS(node.right, parentSum + node.val + leftSum);
    }
    
    getMaxProductDFS(root, 0);
    
    return maxProduct % (Math.pow(10, 9) + 7);
};
Maximum Product of Splitted Binary Tree