823. Binary Trees With Factors

, 
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
class Solution {
    private static final int MOD = 1000000007;

    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        Map<Integer, Integer> numToIndexMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            numToIndexMap.put(arr[i], i);
        }

        // 定义 dp[i] 为 arr[i] 为 root 时的树的个数
        long[] dp = new long[arr.length];
        Arrays.fill(dp, 1); // 当每个数值为 root 且无子节点时

        int count = 1;
        for (int i = 1; i < dp.length; i++) {
            // 枚举左子树
            for (int j = 0; j < i; j++) {
                if (arr[i] % arr[j] == 0) {
                    int target = arr[i] / arr[j];
                    // 注意判空，因为期望的值不一定存在
                    Integer targetIndex = numToIndexMap.get(target);
                    if (targetIndex != null) {
                        dp[i] += dp[j] * dp[targetIndex];
                    }
                }
            }

            count += dp[i] % MOD;
            count %= MOD;
        }

        return count;
    }
}

注意潜在的整数越界问题，所以使用了 long 数组来存储。

References

823. Binary Trees With Factors