问题描述
给定一个数组，数组中的数不重复，且均大于1。要求使用数组中的数构建二叉树，每个数字可以被重复使用，除了叶子节点，每个节点的值等于其子节点的乘积，求构建二叉树的数量，返回的结果mod 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].
原题链接: https://leetcode.com/problems/binary-trees-with-factors/
分析
符合条件的二叉树分为两种情况，一种是单个节节点组成的二叉树， 没有子节点，共有A.length种情况; 另外一种情况是多个节点组成的二叉树，节点的值为children节点值的乘积。第一种情况非常简单，不需要讨论，第二种情况稍微有些复杂，不过我们可以想到：
如果 a = b * c等式成立，那么由a为父节点组成的二叉树的数量 = 由b为父节点组成的二叉树 * 由c为父节点组成的二叉树 * 2 (左右节点交换位置)。
因此对于元素a为root 对应的二叉树数量，我们需要统计出所有b和c所对应的二叉树数量（b < a, c < a）。为了达到这个目的，我们可以使用hashmap存储数据中以任意元素为root所对应的二叉树数量，那么在计算a节点对应的二叉树数量，只需要查询hashmap得到b和c对应的二叉树数量即可，其次为了保证值较小的b和c先于a计算，我们需要对array进行sort，通过bottom to top这种迭代计算得到后续的元素的二叉树数量。
实现
public int umFactoredBinaryTrees(int[] A){
int mod = 1000000007;
Arrays.sort(A);
//key是二叉树root 对应数组中每个值，value是对应二叉树的数量
Map<Integer, Long> map = new HashMap();
Long result = 0;
for(int m = 0; i < A.length; m++){
long cnt = 1; //第一种二叉树情况
int a = A[m];
for(Integer b : map.keySet()){
if(a % b == 0 && map.containsKey(a/b)){
cnt += map.get(b) * map.get(a/b);
}
}
map.put(num, cnt);
result = (result + cnt) % mod;
}
return (int) result;
}
空间复杂度O(n)，时间复杂度O(n^2)