Medium

题目描述

给出一个含有不重复整数元素的数组 arr，每个整数 arr[i] 都大于 1。

用这些整数来构造二叉树，每个整数可以使用任意次。其中：每个非叶节点的值应该等于它的两个子节点值的乘积。

返回我们可以构造的二叉树数量。答案可能很大，返回 答案模 10^9 + 7 的结果。

示例 1：

输入: arr = [2,4]
输出: 3
解释: 我们可以得到这些二叉树: [2], [4], [4, 2, 2]

示例 2：

输入: arr = [2,4,5,10]
输出: 7
解释: 我们可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]

提示：

  • 1 <= arr.length <= 1000
  • 2 <= arr[i] <= 10^9
  • arr 的所有值 互不相同

解题思路

这是一道动态规划题目。核心思路是：对于每个数字作为根节点时，计算有多少种构造方式。

基本思路：

  1. 每个数字都可以单独构成一棵只有根节点的树，这是基础情况
  2. 对于数字 x，如果存在两个数字 a 和 b 使得 a * b = x，那么可以构造以 x 为根、a 和 b 为子节点的树
  3. 构造方式的数量等于以 a 为根的树的数量乘以以 b 为根的树的数量

算法步骤：

  1. 将数组排序，确保处理每个数字时，所有可能的因子都已经被处理过
  2. 使用哈希表存储每个数字对应的树的构造方法数量
  3. 对于每个数字，遍历所有可能的因子对，累加构造方式
  4. 为了避免重复计算，当 a != b 时需要乘以2（因为左右子树可以交换）

时间复杂度优化： 通过排序和哈希表查找，我们可以有效地找到因子对，避免暴力枚举。

代码实现

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& arr) {
        const int MOD = 1000000007;
        sort(arr.begin(), arr.end());
        
        unordered_map<int, long long> dp;
        
        for (int i = 0; i < arr.size(); i++) {
            dp[arr[i]] = 1;
            
            for (int j = 0; j < i; j++) {
                if (arr[i] % arr[j] == 0) {
                    int complement = arr[i] / arr[j];
                    if (dp.count(complement)) {
                        dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[complement]) % MOD;
                    }
                }
            }
        }
        
        long long result = 0;
        for (auto& pair : dp) {
            result = (result + pair.second) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        arr.sort()
        dp = {}
        
        for i, num in enumerate(arr):
            dp[num] = 1
            
            for j in range(i):
                if num % arr[j] == 0:
                    complement = num // arr[j]
                    if complement in dp:
                        dp[num] = (dp[num] + dp[arr[j]] * dp[complement]) % MOD
        
        return sum(dp.values()) % MOD

public class Solution {
    public int NumFactoredBinaryTrees(int[] arr) {
        const int MOD = 1000000007;
        Array.Sort(arr);
        
        var dp = new Dictionary<int, long>();
        
        for (int i = 0; i < arr.Length; i++) {
            dp[arr[i]] = 1;
            
            for (int j = 0; j < i; j++) {
                if (arr[i] % arr[j] == 0) {
                    int complement = arr[i] / arr[j];
                    if (dp.ContainsKey(complement)) {
                        dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[complement]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        foreach (var pair in dp) {
            result = (result + pair.Value) % MOD;
        }
        
        return (int)result;
    }
}

var numFactoredBinaryTrees = function(arr) {
    const MOD = 1000000007;
    arr.sort((a, b) => a - b);
    
    const dp = new Map();
    
    for (let i = 0; i < arr.length; i++) {
        dp.set(arr[i], 1);
        
        for (let j = 0; j < i; j++) {
            if (arr[i] % arr[j] === 0) {
                const other = arr[i] / arr[j];
                if (dp.has(other)) {
                    dp.set(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.get(other)) % MOD);
                }
            }
        }
    }
    
    let result = 0;
    for (let count of dp.values()) {
        result = (result + count) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n²)
空间复杂度O(n)

说明：

  • 时间复杂度：排序需要 O(n log n)，双重循环处理每个数字需要 O(n²)，总体为 O(n²)
  • 空间复杂度：使用哈希表存储每个数字的 DP 值，需要 O(n) 空间