leetcode 823 带因子的二叉树

用动态规划

如果两个节点值不同,要乘2，因为两个节点可以互换位置

dp[i] = dp[left] * dp[right] * 2

如果相同

dp[i] = dp[left] * dp[right]

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;}
}