Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/12/10 17:53)推噓3(3推 0噓 4→)

留言7則, 4人參與討論串132/719 (看更多)

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