力扣刷题记录： 1339. 分裂二叉树的最大乘积

        本题是第174场周赛的 Q3，LC竞赛分为1675.

方法一. 递归（超时）

        单纯使用递归对每一个节点进行遍历，代码如下：

class Solution {
    long long ans = -1;
public:
    int maxProduct(TreeNode* root) {
        long long total_sum = sum(root);

        dfs(root,total_sum);

        return ans%(int)(1e9+7);
    }

    long long sum(TreeNode* root){
        if(root == NULL) return 0;

        return root->val+sum(root->left)+sum(root->right);
    }

    void dfs(TreeNode* root,long long total_sum){
        if(!root) return;

        long long a1 = sum(root);
        long long a2 = total_sum-a1;
        ans = max(a1*a2,ans);

        dfs(root->left,total_sum);
        dfs(root->right,total_sum);
    }
};

方法二. 后序遍历+记忆化搜索(时间超过 11.89% cpp用户)

        后序遍历+记忆化搜索可以让父节点直接用到子节点的结果，从而减少递归调用。代码如下：

class Solution {
    long long ans = -1;
public:
    int maxProduct(TreeNode* root) {
        long long total_sum = sum(root);
        map<TreeNode*,long long> record;
        dfs(root,total_sum,record);

        return ans%(int)(1e9+7);
    }

    long long sum(TreeNode* root){
        if(root == NULL) return 0;

        return root->val+sum(root->left)+sum(root->right);
    }

    void dfs(TreeNode* root,long long total_sum,map<TreeNode*,long long>& record ){
        if(!root) return;

        dfs(root->left,total_sum,record);
        dfs(root->right,total_sum,record);
        long long a1,a2;
        if(record.count(root->left)==1){
            a1 = record[root->left];
        }
        else
            a1 = sum(root->left);
        
        if(record.count(root->right)==1){
            a2 = record[root->right];
        }
        else
            a2 = sum(root->right);
        
        long long sum_tmp = a1 + a2 + root->val;
        record[root] = sum_tmp;
        ans = max(ans,sum_tmp*(total_sum-sum_tmp));
        return;
    }
};