Leetcode 1339. Maximum Product of Splitted Binary Tree

https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/description/

Notes:

This question is a good interview question. The key is how to find the "key points".

It is easy to find the total sum by O(n) where n is the total number of node.

Then we need to split the tree into two part. So if we know the sum of one part, then the other part is also known, since we know the total sum. Then the product also becomes known.

So one of the "key points" is that we need to calculate the sum of one part.

Let us continue.

When the tree is split into two subtrees by removing one edge between two nodes, one of the nodes is always the root of that subtree!

So we just need to calculate the sum of that subtree, which is well known to be done bottom-up recursively. 

The overall time complexity is still O(n), where n is the number of nodes in total.

See the code below:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    int maxProduct(TreeNode* root) {
        sum = calSum(root);
        bottomUpDfs(root);
        return prod%mod;
    }

private:
    int mod = 1e9 + 7, sum = 0;
    long long prod = 0;
    int calSum(TreeNode* root) {
        if(!root) return 0;
        return root->val + calSum(root->left) + calSum(root->right);
    }

    long long bottomUpDfs(TreeNode* root) {
        if(!root) return 0;
        long long localSum = root->val + bottomUpDfs(root->left) + bottomUpDfs(root->right);
        prod = max(prod, localSum*(sum - localSum));
        return localSum;
    }
};