823. 带因子的二叉树

题意

  • 元素都大于1，元素不重复。
  • 计数满足要求的二叉树（每个非叶结点的值应等于它的两个子结点的值的乘积）的数量。
  • 元素可以重复使用。

代码

自上而下动态规划。

  • 所有元素大于1，所以不会有 自己×自己=自己 的情况；
  • 元素本身就是一棵二叉树，所以将 dp 初始化为全 1；
  • 将数组 arr 排序后，遍历数组 arr ，当 arr[i] 为根节点时，其子结点必然在 arr[0] ~ arr[i-1] 之间；
    • 在 arr[0] ~ arr[i-1] 之间寻找 (long long)arr[left] * arr[right] == arr[i]。当 left == right 时，dp[i] += dp[left] * dp[right]；当 left ！= right 时，dp[i] += 2 * dp[left] * dp[right]；
class Solution {public:int MAXN = 1e9 + 7;int numFactoredBinaryTrees(vector<int>& arr) {sort(arr.begin(), arr.end());int n = arr.size();vector<long long> dp(n+1, 1); // 单个根节点的符合要求的二叉树数量就可能溢出，用 longlong// dp[0] = 1;// 最小的数，只有一棵符合要求的二叉树for(int i = 1; i < n; i++){// 子结点只能在 0 ~ i-1 之间（因为元素都大于1）int left = 0, right = i-1;while(left <= right) // 元素可被多次使用，所以要 <={if((long long)arr[left] * arr[right] == arr[i])// 可能溢出，用 longlong{// if(arr[left] != arr[right])元素不会重复，可以直接比较下标if(left != right){dp[i] += 2 * dp[left] * dp[right];}else{dp[i] += dp[left] * dp[right];}left++;}else if((long long)arr[left] * arr[right] <= arr[i])// 可能溢出，用 longlong{left++;}else{right--;}}}long long ans = 0;for(int i = 0; i < n; i++){ans += dp[i];ans = ans % MAXN;}return ans;}};

复杂度

时间复杂度：O(N2)，对每个元素遍历一次其之前的元素。
空间复杂度：O(N)，存储 dp 数组。