[LeetCode] 1339. Maximum Product of Splitted Binary Tree 分裂二叉樹的最大乘積

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.

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)

Constraints:

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

這道題給了一棵二叉樹，說是可以移除任意一條邊，將其分成兩棵子樹，需要將二棵子樹的結點值分別都加起來，然后相乘，讓返回可能最大的乘數，并對一個超大數取余。首先來分析，既然要找到那個最大值，則一定要遍歷每一種情況，即計算斷開每一條邊的情況。那么難點就變成了如何能快速得到斷開形成的兩棵子樹的結點值之和。通過分析例子1可以看出，斷開后的左邊部分形成了根結點為2的一棵新的二叉樹，需要知道其所有結點之和。

此時不難想到，若可以知道以任意結點為根結點的子樹的結點之和，會大大利于計算。而后序遍歷正好符合這種從底向上遍歷的順序，從葉結點開始，不停的往根結點遍歷，同時可以累加遍歷到的結點值，這樣到達根結點時，就可以得到所有的結點值之和了。博主最開始想到的方法是建立每個結點跟以其為根結點的子樹的結點和之間的映射，由于只看了例子1，認為計算乘積的方法就是結點1的映射值減去結點2的映射值，再乘以結點2的映射值就行了。但其實這種方法是不對的，只有在拆分與根結點相連的邊的時候才行，比如例子2，拆分位置結點2的映射值是不包括結點1的，所以計算的結果肯定不對。

正確的方法是用整個樹所有的結點值之和，減去斷開點為根結點的子樹之和，所以先要求出所有的結點之和，這里可以快速用一個先序遍歷來得到，然后再用一個后序遍歷來計算乘積，該遞歸函數的返回值是以輸入的結點為根結點的子樹的結點之和，乘積保存在引用參數 res 里。在后序遍歷中，首先判空，若當前結點為空，則返回0，否則計算以當前結點為根結點的子樹的結點之和，方法是當前結點值加上對左子結點調用遞歸的返回值，再加上對右子結點調用參數的返回值。此時更新乘積結果 res，用上面算出的結果 cur，乘以整個樹結點之和 sum 減去 cur 的值即可，參見代碼如下：

解法一：

class Solution {
public:
    int maxProduct(TreeNode* root) {
        long res = 0, sum = 0, M = 1e9 + 7;
        dfs(root, sum);
        helper(root, sum, res);
        return res % M;
    }
    void dfs(TreeNode* node, long& sum) {
        if (!node) return;
        sum += node->val;
        dfs(node->left, sum);
        dfs(node->right, sum);
    }
    int helper(TreeNode* node, long sum, long& res) {
        if (!node) return 0;
        int cur = node->val + helper(node->left, sum, res) + helper(node->right, sum, res);
        res = max(res, cur * (sum - cur));
        return cur;
    }
};

再來看一種更簡潔的寫法，這里并不需要一個單獨的遞歸函數來計算整棵樹的結點之和，而是可以利用上面的后序遍歷的遞歸函數，因為其返回的就是以輸入結點為根結點的子樹的結點之和，而若輸入的就是原來的根結點，則得到的就是整棵樹的結點值和。但是由于此時輸入的 sum 是0，所以得到的 res 結果也沒有意義，需要再次調用遞歸函數，此時的 sum 就可以傳入正確的值了，從而得到的 res 也是正確的，參見代碼如下：

解法二：

class Solution {
public:
    int maxProduct(TreeNode* root) {
        long res = 0, sum = 0, M = 1e9 + 7;
        sum = dfs(root, sum, res);
        dfs(root, sum, res);
        return res % M;
    }
    int dfs(TreeNode* node, long sum, long& res) {
        if (!node) return 0;
        int cur = node->val + dfs(node->left, sum, res) + dfs(node->right, sum, res);
        res = max(res, cur * (sum - cur));
        return cur;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1339

類似題目：

Count Nodes With the Highest Score

參考資料：

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

https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/solutions/496496/java-two-pass-postorder-traversal/

https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/solutions/496549/java-c-python-easy-and-concise/

LeetCode All in One 題目講解匯總(持續更新中...)