[LeetCode]Binary Trees With Factors

这道题和Unique BST的做法是十分类似的。我们需要计算对于每一个数，当其为根的时候有多少个不同的二叉树。我们把输入数组从小到大排列，然后对于第i个数为根的情况，遍历所有i之前的数，看是否有对应的数可以与其相乘为第i个数。假设排序后的数组为A，我们找到了A[j]和A[k]其满足A[j] * A[k] == A[i], 其中j <= k < i。注意我们只需要扫到A[j] * A[j] <= A[i]的情况，因为A[j]为左子树A[k]为右子树的情况和A[k]为左子树A[j]为右子树的情况是一样的，如果k和j不同，只需要乘以2即可; 如果k和j相同，我们不需要乘以2，否则会造成重复。我们有递推公式：

• dp[A[i]] = 1, 初始状况，大小为1的树。
• 当我们找到一对k, j，其满足情况A[j] * A[k] == A[i], 其中j <= k < i
• 如果j != k, dp[A[i]] += 2 * dp[A[j]] * dp[A[k]]
• 如果j == k, dp[A[i]] += dp[A[j]] * dp[A[k]]

时间复杂度O(n^2)，空间复杂度O(n)，代码如下：