Given an array of unique integers, each integer is strictly greater than 1.
We make a binary tree using these integers and each number may be used for any number of times.
Each non-leaf node's value should be equal to the product of the values of it's children.
How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.
Example 1:
Input:A = [2, 4]
Output: 3 Explanation: We can make these trees:[2], [4], [4, 2, 2]
Example 2:
Input:A = [2, 4, 5, 10]
Output:7
Explanation: We can make these trees:[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]
.
Note:
1 <= A.length <= 1000
.2 <= A[i] <= 10 ^ 9
.
带因子的二叉树。
给出一个含有不重复整数元素的数组,每个整数均大于 1。
我们用这些整数来构建二叉树,每个整数可以使用任意次数。
其中:每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个?返回的结果应模除 10 ** 9 + 7。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-trees-with-factors
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题虽然说的是构建树,但是其实是一道数学题。思路是hashmap + sort。既然树的构建需要满足root.val = root.left.val * root.right.val,那么先把input排序,这样在找孩子节点的时候会方便很多。接着我们遍历input数组,假设每一个遍历到的节点都可以当做根节点,那么此时我们再去找满足题意的孩子节点。对于一个潜在的root.val nums[i],我们要找的是数组内是否含有一个 nums[j] 满足 nums[i] % nums[j] == 0 同时 nums[i] / nums[j] 也在hashmap中。如果有这样的组合,那么说明我们就能构建一棵符合题意的树。记得最后要对结果取模。
时间O(n^2)
空间O(n)
Java实现
1 class Solution { 2 public int numFactoredBinaryTrees(int[] nums) { 3 // corner case 4 if (nums == null || nums.length == 0) { 5 return 0; 6 } 7 8 // normal case 9 int MOD = (int) Math.pow(10, 9) + 7; 10 int len = nums.length; 11 long res = 0; 12 Arrays.sort(nums); 13 HashMap<Integer, Long> map = new HashMap<>(); 14 // 每个数字默认都可以组成一个以自己为根节点的树 15 for (int num : nums) { 16 map.put(num, 1L); 17 } 18 19 for (int i = 0; i < len; i++) { 20 long count = map.get(nums[i]); 21 for (int j = 0; j < i; j++) { 22 // 如果j能被i整除同时i / j的商也在hashmap中,那么就可以累加 23 if (nums[i] % nums[j] == 0 && map.containsKey(nums[i] / nums[j])) { 24 count += map.get(nums[j]) * map.get(nums[i] / nums[j]); 25 } 26 } 27 map.put(nums[i], count); 28 res = (res + count) % MOD; 29 } 30 return (int) res; 31 } 32 }