leetcode 823. Binary Trees With Factors（因子二叉树）

Given an array of unique integers, arr, where each integer arr[i] 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 its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 10⁹ + 7.

Example 1:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]
Example 2:

Input: arr = [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].

Constraints:
1 <= arr.length <= 1000
2 <= arr[i] <= 10⁹
All the values of arr are unique.

数组里面的数字可用来作树的节点，可以重复使用。
非叶子的节点的数字要等于它的children节点的乘积。
节点可以单独组成二叉树。

问可以组成多少个这样的二叉树。

思路：

首先想到的是要从小到大组成树，这样大的数字才能是小的数字的乘积，所以要把数组排序。

然后可以想到的是root的个数应该是左子树个数与右子树个数的乘积，
比如左子树有5种，右子树有6种，
那么左边的每一种都可以对应右边的6种，所以是乘法。

那么每次是不是都需要计算左右子树的个数？如果都计算，遇到重复的数字就会发生重复的计算，
所以要用DP，保存已经计算好的。

用dp[i]表示数字 ℹ 可以形成的二叉树个数。
每个数字可单独形成二叉树，所以dp[i] = 1。

arr[i]不是连续的数字，所以用hashMap作为dp数组，
从小到大遍历数字，遇到ℹ 是2个数乘积的，dp[i] += dp[左] * dp[右], 其中左 ✖ 右 = ℹ

最后把hashMap中的value相加。

注意相加时可能超出int的最大范围，所以用long, 不要忘了 % mod。

public int numFactoredBinaryTrees(int[] arr) {
    int n = arr.length;
    int mod = 1000000007;
    Long res = 0l;
    HashMap<Integer, Long> dp = new HashMap<>();
    
    Arrays.sort(arr);
    
    for(int i = 0; i < n; i ++) {  //arr下标
        dp.put(arr[i], 1l);
        for(int j = 0; j < i; j ++) {  //arr下标
            if(arr[i] % arr[j] == 0 && dp.containsKey(arr[i] / arr[j])) {
                dp.put(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.get(arr[i]/arr[j]))%mod);
            }
        }
    }
    for(Long values : dp.values()) {
        res += values;
    }
    return (int)(res % mod);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21