Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

1339. Maximum Product of Splitted Binary Tree
給予你一個二元樹，求出把該樹拆分成兩個樹之後，該兩個樹的所有元素和的最大乘積
（因為數字很大，所以返回值要模[10^9+ 7]）

Example:
https://assets.leetcode.com/uploads/2020/01/21/sample_1_1699.png
Input: root = [1,2,3,4,5,6]
Output: 把樹拆成 t1 = [4,2,5] 和 t2 = [1,null,3,6] sum(t1) = 11 sum(t2) = 10
該兩數相乘會是最大的積。

思路：
1.因為要將樹拆成兩個和，我們可以透過整個樹的和total減去當前節點作為root的子樹和
  來得到把樹分成兩堆後兩個樹分別的和。
2.dfs每一個節點並計算兩堆樹的內積並更新最大數值。
3.因為太多getSum()的重複計算吃了TLE，所以用了一個 Map來Memoization。

Java Code：
------------------------------------
class Solution {
    private long maxProduct = 0;
    private int totalSum = 0;
    private Map<TreeNode, Integer> sumMap;

    public int maxProduct(TreeNode root) {
        sumMap = new HashMap<>();
        totalSum = getSum(root);
        getProduct(root);
        return (int) (maxProduct % 1000000007);
    }

    private int getSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        if (sumMap.containsKey(node)) {
            return sumMap.get(node);
        }
        int sum = node.val + getSum(node.left) + getSum(node.right);
        sumMap.put(node, sum);
        return sum;
    }

    private void getProduct(TreeNode node) {
        if (node == null) {
            return;
        }
        int leftSum = getSum(node.left);
        int rightSum = getSum(node.right);
        int currentSum = node.val + leftSum + rightSum;
        long currentProduct = (long) currentSum * (totalSum - currentSum);

        maxProduct = Math.max(maxProduct, currentProduct);
        getProduct(node.left);
        getProduct(node.right);
    }
}
------------------------------------

AC是AC了但是只有18% ☹

--
https://i.imgur.com/bFRiqA3.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1670665982.A.DD1.html
→ wwndbk: 啥18？速度嗎
→ Rushia: Runtime 37ms beats18.99%
推 pandix: 有記的話 currentSum = getSum(node); 就可以了吧
→ Rushia: 可以欸 可是效率還是差不多爛
推 AyuniD: AC 但 8.32/10.70 xddddd
推 AyuniD: 哦不對 我用你的邏輯就 7x% 然後再用回我的就更快==
→ AyuniD: LC 的時間真的參考就好欸。。。
※ 編輯: Rushia (122.100.75.86 臺灣), 12/11/2022 23:11:22