友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
823. 带因子的二叉树
给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个？答案可能很大，返回 对 109 + 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] <= 109 -
arr中的所有值 互不相同
思路分析
斐波那契式的动态规划。子树还有子树，递归看去，就是更小规划的问题。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-07-16 21:31:41
*/
public int numFactoredBinaryTrees(int[] arr) {
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int i : arr) {
map.put(i, new HashSet<>());
}
Arrays.sort(arr);
for (int num : arr) {
Set<Integer> set = map.get(num);
for (int j = 0; arr[j] < num; j++) {
int diff = num / arr[j];
if (num % arr[j] == 0 && map.containsKey(diff)) {
set.add(arr[j]);
set.add(diff);
}
}
}
int MOD = 1_000_000_007;
Map<Integer, Long> memo = new HashMap<>();
long result = 0;
for (int num : arr) {
long temp = dfs(map, MOD, num, memo) % MOD;
result = (result + temp) % MOD;
}
return (int) result;
}
private long dfs(Map<Integer, Set<Integer>> map, int MOD,
int num, Map<Integer, Long> memo) {
if (memo.containsKey(num)) {
return memo.get(num);
}
long result = 1;
Set<Integer> set = map.get(num);
for (Integer in : set) {
// 注意：这里应该使用乘法原理！
long a = dfs(map, MOD, in, memo);
long b = dfs(map, MOD, num / in, memo);
long temp = (a * b) % MOD;
result = (result + temp) % MOD;
}
result %= MOD;
memo.put(num, result);
return result;
}