Leetcode/src/main/java/com/fishercoder/solutions/secondthousand/_1339.java at master · fishercoder1534/Leetcode · GitHub

Name: Leetcode/src/main/java/com/fishercoder/solutions/secondthousand/_1339.java at master · fishercoder1534/Leetcode · GitHub
Rating: 4.4 (2080 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
packagecom.fishercoder.solutions.secondthousand;

importcom.fishercoder.common.classes.TreeNode;
importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.HashSet;
importjava.util.List;
importjava.util.Map;
importjava.util.Set;

publicclass_1339 {
publicstaticclassSolution1 {
publicintmaxProduct(TreeNoderoot) {
Set<Long> set = newHashSet<>();
longtotal = postOrder(root, set);
longresult = 0L;
for (longsum : set) {
result = Math.max(result, sum * (total - sum));
 }
return (int) (result % 1000000007);
 }

privatelongpostOrder(TreeNoderoot, Set<Long> set) {
if (root == null) {
return0;
 }
longleftSum = postOrder(root.left, set);
longrightSum = postOrder(root.right, set);
longsum = root.val + leftSum + rightSum;
set.add(sum);
returnsum;
 }
 }

publicstaticclassSolution2 {
/*
 * My completely original solution, but much more verbose and uses more extra space.
 */
publicintmaxProduct(TreeNoderoot) {
Map<TreeNode, Long> sumMap = newHashMap<>();
longtotalSum = postOrderBuildSumMap(root, sumMap);
sumMap.put(root, totalSum);
List<long[]> productList = newArrayList<>();
postOrderBuildProductList(root, sumMap, productList, sumMap.get(root));
longresult = 0L;
doublemodulo = Math.pow(10, 9) + 7;
for (long[] p : productList) {
longproduct = p[0] * p[1];
result = Math.max(result, product);
 }
return (int) (result % modulo);
 }

privatevoidpostOrderBuildProductList(
TreeNoderoot, Map<TreeNode, Long> sumMap, List<long[]> productList, Longtotal) {
if (root == null) {
return;
 }
if (root.left == null && root.right == null) {
return;
 }
postOrderBuildProductList(root.left, sumMap, productList, total);
postOrderBuildProductList(root.right, sumMap, productList, total);
if (root.left != null) {
// suppose we cut off left subtree now
longleftSum = sumMap.get(root.left);
longremainder = total - leftSum;
productList.add(newlong[] {leftSum, remainder});
 }
if (root.right != null) {
// suppose we cut off right subtree now
longrightSum = sumMap.get(root.right);
longremainder = total - rightSum;
productList.add(newlong[] {rightSum, remainder});
 }
 }

privatelongpostOrderBuildSumMap(TreeNoderoot, Map<TreeNode, Long> sumMap) {
if (root == null) {
return0L;
 }
longleftSum = postOrderBuildSumMap(root.left, sumMap);
longrightSum = postOrderBuildSumMap(root.right, sumMap);
longsum = leftSum + rightSum + root.val;
sumMap.put(root, sum);
returnsum;
 }
 }
}