1339. 分裂二叉樹的最大乘積

思路

設一整棵樹的數值總和是sum，子樹可能的總和是a，那麼最大乘積就是max(a * (sum - a))。

計算子樹總合的過程可以用dfs，相比bfs要好寫得多。
dfs(TreeNode* node)代表以node為根結點的整棵樹的合。
在計算過程一併紀錄所有子樹和。最後一個個去嘗試誰乘積比較大即可。

再找最大乘積時，越靠近sum / 2的數值能得到越大的結果（把一個數拆成兩個，問怎麼拆相乘最大），能用這個特性去判斷答案。

因為最多只會有50000個節點，且值最多10000，用int可以表示合，只有相乘才會溢出。

程式碼

dfs

class Solution {
public:
    int maxProduct(TreeNode* root) {    
        const int MOD = 1e9 + 7;
        vector<int> possibleSum;
        auto dfs = [&](this auto&&dfs, TreeNode* node) -> int {
            if(!node) return 0;
            // 整棵樹的合 = 自己 + 左子樹的合 + 右子樹的合。
            int cur = node->val + dfs(node->left) + dfs(node->right); 
            possibleSum.push_back(cur);
            return cur;
        };
        int sum = dfs(root);
        
        long long res = 0;
        for(int a : possibleSum) {
            res = max(res, 1LL * a * (sum - a));
        }
        return res % MOD;
    }
};

複雜度分析

• 時間複雜度：$O(n)$，每個節點走訪一遍
• 空間複雜度：$O(n)$，紀錄子樹的合。