0823：带因子的二叉树（1899 分）

力扣第 823 题

题目

给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。

用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个？答案可能很大，返回 对 109 + 7 取余 的结果。

示例 1:

输入: arr = [2, 4]
输出: 3
解释: 可以得到这些二叉树: [2], [4], [4, 2, 2]

示例 2:

输入: arr = [2, 4, 5, 10]
输出: 7
解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

提示：

• 1 <= arr.length <= 1000
• 2 <= arr[i] <= 109
• arr 中的所有值 互不相同

分析

非叶节点显然大于子节点，于是考虑将 arr 排序，然后遍历 arr[j] 作为根节点的情况。

arr[j] 为根节点，然后遍历前面的 arr[i]，如果 arr[j]/arr[i] 也在 arr 中存在，即可转为递归子问题。

为了方便递归，令 dp[x] 代表根节点值为 x 的二叉树个数。x 的值稀疏，因此用哈希表存储。

解答

1
2
3
4
5
6
7
8
9

def numFactoredBinaryTrees(self, arr: List[int]) -> int:
    res, mod = 0, 10**9+7
    d = defaultdict(lambda: 1)
    for x in sorted(arr):
        for y in list(d):
            if x%y==0 and x//y in d:
                d[x] = (d[x]+d[y]*d[x//y])%mod
        res = (res+d[x])%mod
    return res

240 ms