問題描述

給你一棵二叉樹，它的根為 root 。請你刪除 1 條邊，使二叉樹分裂成兩棵子樹，且它們子樹和的乘積盡可能大。
由于答案可能會很大，請你將結(jié)果對 10^9 + 7 取模后再返回。

Example

輸入：root = [1,2,3,4,5,6]
輸出：110
解釋：刪除紅色的邊，得到 2 棵子樹，和分別為 11 和 10 。它們的乘積是 110 （11*10）

題目鏈接：1339. 分裂二叉樹的最大乘積 (難度:中等)

思路

這個問題的一個關(guān)鍵是如何計算刪除邊后的兩棵子樹和。這里可以采用前綴和的思想，比如假設(shè)整棵二叉樹的和為 total, 則將 root 和 root->left 之間的邊刪除后，root 所在的子樹和 = total - 以 root->left 為根節(jié)點的子樹和。因此，我們可以使用先序遍歷先求出 total，然后利用后序遍歷枚舉所有的子樹和，同時記錄最大積。這里要注意的是，使用 max 的時候不要進行取模操作，因為大的數(shù)取模后未必比小的數(shù)要大。因此我們用 long long 保存結(jié)果，并對最終結(jié)果進行取模。

代碼：

class Solution {
public:
    static const int MOD = (int)1e9 + 7;
    long long ans = LLONG_MIN;
    long long Sum(TreeNode* root){
        if(root == NULL)
            return 0;
        return root->val + Sum(root->left) + Sum(root->right);
    }
    long long helper(TreeNode* root, long long total){
        if(root == NULL)
            return 0;
        long long l_sum = helper(root->left, total);
        long long r_sum = helper(root->right, total);
        long long l_product = (total - l_sum) * l_sum;
        long long r_product = (total - r_sum) * r_sum;
        ans = max(ans, max(l_product, r_product));
        return root->val + l_sum + r_sum;
    }
    int maxProduct(TreeNode* root) {
        long long total = Sum(root);
        helper(root, total);
        return ans % MOD;
    }
};

執(zhí)行結(jié)果：260ms, 88.7 MB