823. Binary Trees With Factors 带因子的二叉树

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

@TOC

题目地址：https://leetcode.com/problems/binary-trees-with-factors/description/

题目描述

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. 1 <= A.length <= 1000.
2. 2 <= A[i] <= 10 ^ 9.

题目大意

给定了一个数组，可以从这个数组中选取任意多的节点构建成二叉树，要求二叉树中的非叶子节点的值必须等于其子节点的和。问有多少种组合方案。

解题方法

动态规划

题目出现了DP的最最明显提示：需要对结果求模！这个说明结果很大，必须通过DP求解了。

方法其实很简单的，首先需要先排序，注意到题目中说了数组是Unique的，所以每个数字出现的次数只有1次。使用dp数组保存每个数字作为根节点的情况下能构建出的所有二叉树数目，求法是遍历所有小于自己的数字取值作为左子树，然后把根节点/左子树的值当做右节点，然后对他们能组成的二叉树数目乘积求和。

dp[i] = sum(dp[j] * dp[i / j])
res = sum(dp[i])

需要注意的是，一定要保证根节点/左子树的结果是整数，而且也在dp内，才去做状态转移。因为，题目给的每个数字都是大于1的，因此根节点/左子树一定小于根节点，所以直接判断它是否在dp里出现过就行了，它不可能在更后面才出现。

时间复杂度是O(NlogN + N)，空间复杂度是O(N).

class Solution(object):
    def numFactoredBinaryTrees(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        A.sort()
        dp = {}
        for i, a in enumerate(A):
            dp[a] = 1
            for j in range(i):
                if a % A[j] == 0 and a / A[j] in dp:
                    dp[a] += dp[A[j]] * dp[a / A[j]]
        return sum(dp.values()) % (10**9 + 7)

相似题目

参考资料

https://leetcode.com/problems/binary-trees-with-factors/discuss/125794/C++JavaPython-DP-solution

日期

2018 年 10 月 30 日 —— 啊，十月过完了