用动态规划
如果两个节点值不同,要乘2，因为两个节点可以互换位置
dp[i] = dp[left] * dp[right] * 2
如果相同文章来源：https://www.toymoban.com/news/detail-681562.html
dp[i] = dp[left] * dp[right]文章来源地址https://www.toymoban.com/news/detail-681562.html
class Solution {
public int numFactoredBinaryTrees(int[] arr) {
Arrays.sort(arr);
int n = arr.length;
long[] dp = new long[n];
long res = 0, mod = 1000000007;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int left = 0, right = i - 1; left <= right; left++) {
while (right >= left && (long) arr[left] * arr[right] > arr[i]) {
right--;
}
if (right >= left && (long) arr[left] * arr[right] == arr[i]) {
if (right != left) {
dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod;
} else {
dp[i] = (dp[i] + dp[left] * dp[right]) % mod;
}
}
}
res = (res + dp[i]) % mod;
}
return (int) res;
}
}
到了这里，关于leetcode 823 带因子的二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
