|
5 | 5 | importjava.util.HashSet; |
6 | 6 | importjava.util.Set; |
7 | 7 |
|
| 8 | +/** |
| 9 | + * 1343. Maximum Product of Splitted Binary Tree |
| 10 | + * |
| 11 | + * Given a binary tree root. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized. |
| 12 | + * Since the answer may be too large, return it modulo 10^9 + 7. |
| 13 | + * |
| 14 | + * Example 1: |
| 15 | + * Input: root = [1,2,3,4,5,6] |
| 16 | + * Output: 110 |
| 17 | + * Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10) |
| 18 | + * |
| 19 | + * Example 2: |
| 20 | + * Input: root = [1,null,2,3,4,null,null,5,6] |
| 21 | + * Output: 90 |
| 22 | + * Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6) |
| 23 | + * |
| 24 | + * Example 3: |
| 25 | + * Input: root = [2,3,9,10,7,8,6,5,4,11,1] |
| 26 | + * Output: 1025 |
| 27 | + * |
| 28 | + * Example 4: |
| 29 | + * Input: root = [1,1] |
| 30 | + * Output: 1 |
| 31 | + * |
| 32 | + * Constraints: |
| 33 | + * Each tree has at most 50000 nodes and at least 2 nodes. |
| 34 | + * Each node's value is between [1, 10000]. |
| 35 | + * */ |
8 | 36 | publicclass_1343 { |
9 | 37 | publicstaticclassSolution1 { |
10 | 38 | publicintmaxProduct(TreeNoderoot) { |
|