Re: [閒聊] 每日LeetCode

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？速度嗎 12/10 17:53

→ Rushia: Runtime 37ms beats18.99% 12/10 17:54

推 pandix: 有記的話 currentSum = getSum(node); 就可以了吧 12/10 18:20