LeetCode 823. 带因子的二叉树

2024-03-11 HGNULB 约 14 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 823. 带因子的二叉树

题意分析

给定一个各元素互不相同、且都大于 1 的整数数组 arr，用这些数作为节点值构造二叉树。每个值可以重复使用任意多次，但每个非叶节点的值必须等于它两个子节点值的乘积。求能构造出多少棵这样的树，结果对 $10^9+7$ 取模。

先把规则读细。「非叶节点的值等于两个子节点的乘积」隐含了一个重要事实：每个非叶节点必须恰好有两个孩子，不存在只有一个孩子的节点——否则乘积无从谈起。所以合法的树要么是单个叶子，要么每个内部节点都是满二叉的。

「每个值可以重复使用任意多次」意味着不同子树可以复用同一个数，甚至左右子树可以是完全相同的两棵树（当根值是完全平方数且平方根在数组里时）。

还有一处必须明确：左右子树是有区别的。同一个乘积分解 $x = a \times b$（$a \ne b$）会产生两棵不同的树——$a$ 在左 $b$ 在右，和 $a$ 在右 $b$ 在左。所以枚举因子对时要枚举有序对，不能只枚举一半再乘二（乘二会在 $a = b$ 时多算）。

约束是 $1 \le n \le 1000$，$2 \le arr[i] \le 10^9$，元素互不相同。$n$ 只有一千，$O(n^2)$ 是四十万次操作，完全允许「对每个数枚举所有可能的较小因子」；而值域高达 $10^9$ 则排除了任何按数值开数组的做法，只能用哈希表做「值 → 位置」的映射。「元素互不相同」这条保证了映射是单射，不需要处理重复键。

边界方面：每个数自己就能构成一棵单节点的树，所以答案至少是 $n$；数组只有一个元素时答案就是 1；所有元素都是质数时，任何数都无法被分解，答案恰好是 $n$。

解法：排序 + DP + 哈希表

核心思路

暴力思路是递归构造：以每个值为根，枚举所有分解方式，递归地构造左右子树并计数。这会重复计算大量相同的子问题——以值 $x$ 为根的树的数量，只取决于 $x$ 本身，与它出现在哪棵大树的哪个位置无关。这个观察直接指向记忆化，也就是动态规划。

显式写下状态定义：$dp[i]$ 表示以 arr[i] 这个值作为根节点，能构造出的二叉树的数量。

转移基于「根值等于两子节点乘积」这条规则。以 $x = arr[i]$ 为根的树分两类：

$x$ 单独成为叶子，这算一棵树，贡献 1。这就是 $dp$ 的初始值。

$x$ 有两个孩子，设左孩子的值是 $a$、右孩子的值是 $b$，则必须 $a \times b = x$，且 $a$、$b$ 都要出现在数组里。此时左子树的形态数是 $dp[a]$、右子树的形态数是 $dp[b]$，两者独立，所以这一对分解贡献 $dp[a] \times dp[b]$ 棵树。

于是转移式是

$dp[i] = 1 + \sum_{a \cdot b = arr[i],\ a,b \in arr} dp[a] \cdot dp[b]$

求和遍历的是有序对，所以 $a$ 从数组中所有可能的因子里取，$b$ 由 $arr[i] / a$ 唯一确定。当 $a \ne b$ 时，$(a,b)$ 与 $(b,a)$ 会被分别枚举到，恰好对应两棵不同的树；当 $a = b$（根值是完全平方数）时只被枚举一次，贡献 $dp[a]^2$，也正确。这就是为什么直接枚举有序对比「枚举无序对再乘二」更省心。

接下来是两个让转移能落地的技术选择。

第一，先把数组升序排序。 因为 $arr[i]$ 的任何真因子都严格小于它自身（数组元素都大于 1），排序后这些因子必然位于更靠前的下标上，$dp$ 值已经计算完毕。这就建立了合法的计算顺序——本质上是给这个隐式的依赖图做了拓扑排序，而排序恰好是它最简单的实现。

第二，用哈希表建立「值 → 下标」的映射。 枚举因子 $a = arr[j]$（$j < i$）后，另一个因子是 $arr[i] / arr[j]$，需要在 $O(1)$ 时间判断它是否在数组中并取出它的 $dp$ 值。值域到 $10^9$，只能用哈希表。

有了这两点，内层循环就变成：对每个 $j < i$，先判断 $arr[i] \bmod arr[j] = 0$（不整除就不可能构成分解），再查另一个因子是否存在，存在则累加 $dp[j] \times dp[k]$。

最后一个细节是取模与溢出。$dp$ 值都已对 $10^9+7$ 取模，两者相乘可达 $10^{18}$ 量级，超出 32 位整型的范围，所以 $dp$ 数组必须用 64 位整型，且乘完立即取模。

答案是所有 $dp[i]$ 之和——每棵树都有唯一的根，按根分类求和不重不漏。

解题步骤

第一步，把 arr 升序排序。 为什么必须排序：转移要用到两个因子的 $dp$ 值，而因子严格小于被分解的数。排序保证了「计算 $dp[i]$ 时，所有比 $arr[i]$ 小的数的 $dp$ 都已就绪」，这是整个递推的合法性前提。不排序的话，$dp[k]$ 可能还是初始值 1，导致漏算。

第二步，建立「值 → 下标」的哈希映射。 为什么用哈希表而不是二分查找：两者都可行，哈希是 $O(1)$、二分是 $O(\log n)$，在 $O(n^2)$ 的内层循环里哈希更划算；更关键的是值域 $10^9$ 排除了直接开数组的可能。为什么可以放心用值作键：题目保证元素互不相同。

第三步，把所有 $dp[i]$ 初始化为 1。 为什么初值是 1 而不是 0：每个值自身就是一棵合法的单节点树。这个 1 不是「空树」也不是占位符，而是一个真实的计数，写成 0 会让所有答案系统性偏小。

第四步，外层 $i$ 从小到大遍历，内层 $j$ 从 0 到 $i-1$ 遍历。 为什么内层上界是 $i$ 而不是 $n$：因子必须严格小于当前值，$j \ge i$ 的元素不小于 $arr[i]$，不可能是它的真因子。把上界写成 $n$ 虽然靠整除判断也能筛掉大部分，但会引入 $arr[j] = arr[i]$ 时另一个因子为 1 的情形，而 1 不在数组里，恰好被哈希查询挡住——不出错但白跑一半循环。

第五步，若 $arr[i] \bmod arr[j] \ne 0$ 就跳过。 为什么先判整除：只有整除才可能构成乘积分解，这一步是最廉价的过滤，能挡掉绝大多数无效的 $j$。

第六步，计算另一个因子 $right = arr[i] / arr[j]$，在哈希表中查它的下标 $k$；存在则令 $dp[i] \leftarrow (dp[i] + dp[j] \times dp[k]) \bmod (10^9+7)$。 为什么是相乘而不是相加：左右子树的选择相互独立，方案数是乘法关系。为什么 $k$ 可以等于 $j$：当 $arr[i]$ 是完全平方数且平方根在数组里时，左右子树用同一个值，$dp[j] \times dp[j]$ 正是这种情形的方案数，不需要特殊处理。

第七步，把所有 $dp[i]$ 求和并取模，返回结果。 为什么按根求和不会重复：每棵树的根是唯一确定的，按根分类是一个不重不漏的划分。

以 arr = [2, 4, 5, 10] 走一遍（期望答案 7）。

排序后仍是 [2, 4, 5, 10]。哈希映射为 $2 \to 0$、$4 \to 1$、$5 \to 2$、$10 \to 3$。初始 $dp = [1, 1, 1, 1]$。

$i = 0$（值 2）：内层循环范围为空，$dp[0]$ 保持 1。含义是 2 是质数，只能作单节点树。

$i = 1$（值 4）：$j = 0$，$arr[0] = 2$，$4 \bmod 2 = 0$，另一个因子是 $4 / 2 = 2$，哈希查到下标 0。累加 $dp[0] \times dp[0] = 1 \times 1 = 1$，$dp[1] = 1 + 1 = 2$。含义是以 4 为根有两棵树：单节点的 4，以及左右孩子都是 2 的 4(2,2)。注意这里 $j = k = 0$，左右子树用了同一个值，只被枚举一次，贡献 1——如果按「枚举无序对再乘二」处理，这里会错误地算成 2。

$i = 2$（值 5）：$j = 0$ 时 $5 \bmod 2 = 1$，跳过；$j = 1$ 时 $5 \bmod 4 = 1$，跳过。$dp[2]$ 保持 1。5 是质数。

$i = 3$（值 10）：
$j = 0$，$arr[0] = 2$，$10 \bmod 2 = 0$，另一因子 $10/2 = 5$，哈希查到下标 2。累加 $dp[0] \times dp[2] = 1 \times 1 = 1$，$dp[3] = 2$。这对应树 10(2,5)。
$j = 1$，$arr[1] = 4$，$10 \bmod 4 = 2 \ne 0$，跳过。
$j = 2$，$arr[2] = 5$，$10 \bmod 5 = 0$，另一因子 $10/5 = 2$，哈希查到下标 0。累加 $dp[2] \times dp[0] = 1$，$dp[3] = 3$。这对应树 10(5,2)——与上一棵是左右镜像，属于两棵不同的树。这一步正是「枚举有序对」的价值所在：同一个无序分解 ${2,5}$ 被 $j=0$ 和 $j=2$ 各枚举一次，自动得到 2 的计数。

最终 $dp = [1, 2, 1, 3]$，求和得 $1 + 2 + 1 + 3 = 7$。

逐一列出这 7 棵树验证：单节点的 2、4、5、10 共 4 棵；4(2,2) 1 棵；10(2,5) 与 10(5,2) 共 2 棵。合计 7，与计算结果一致。

代码实现

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        long mod = 1_000_000_007L;
        Arrays.sort(arr);

        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            indexMap.put(arr[i], i);
        }

        long[] dp = new long[arr.length];
        Arrays.fill(dp, 1);

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] % arr[j] != 0) {
                    continue;
                }
                int right = arr[i] / arr[j];
                Integer k = indexMap.get(right);
                if (k != null) {
                    dp[i] = (dp[i] + dp[j] * dp[k]) % mod;
                }
            }
        }

        long answer = 0;
        for (long v : dp) {
            answer = (answer + v) % mod;
        }
        return (int) answer;
    }
}

func numFactoredBinaryTrees(arr []int) int {
    const MOD int64 = 1_000_000_007

    sort.Ints(arr)
    n := len(arr)

    indexMap := make(map[int]int, n)
    for i, v := range arr {
        indexMap[v] = i
    }

    dp := make([]int64, n)
    for i := range dp {
        dp[i] = 1
    }

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if arr[i]%arr[j] == 0 {
                right := arr[i] / arr[j]
                if k, ok := indexMap[right]; ok {
                    dp[i] = (dp[i] + dp[j]*dp[k]) % MOD
                }
            }
        }
    }

    var answer int64
    for _, v := range dp {
        answer = (answer + v) % MOD
    }
    return int(answer)
}

复杂度分析

时间复杂度：$O(n^2)$。排序是 $O(n \log n)$，建映射是 $O(n)$，主循环是标准的双层枚举 $O(n^2)$，每次内层迭代只做一次取模、一次除法和一次哈希查询，都是常数。$n \le 1000$ 时约 $5 \times 10^5$ 次内层迭代，运行时间可以忽略。注意这里不能改成「对每个 $x$ 枚举到 $\sqrt{x}$」——值域到 $10^9$，$\sqrt{x}$ 是 $3 \times 10^4$ 量级，反而比枚举数组里的 $n \le 1000$ 个候选更慢。

空间复杂度：$O(n)$。$dp$ 数组和哈希映射各占 $O(n)$。这里的哈希表是不可省的——值域 $10^9$ 让「值 → 下标」无法用数组直接索引。

关键点总结

子问题只与「根的值」有关，与它所处的位置无关，这是可以做动态规划的判据。识别出这一点之后，状态定义 $dp[值]$ 几乎是自动写出来的。凡是递归构造类的计数题，先问一句「这个子问题的结果依赖哪些参数」，参数越少越好做。

排序为隐式的依赖图提供了拓扑序。因子严格小于原数，所以升序处理就保证了「用到的 $dp$ 都已算好」。这个技巧在最大整除子集、整数拆分等题里通用——凡是依赖关系与数值大小同向，排序就是最省事的拓扑排序。

枚举有序对可以自动处理左右子树的区分与自乘的特例。直接对每个 $j$ 枚举，让 $(a,b)$ 与 $(b,a)$ 各来一次，$a = b$ 时只来一次，正好对应实际的树数量。相比「枚举一半再乘二、遇到平方数特判」的写法，出错面小得多。

值域大而元素少，就用哈希表把值映射成下标。$10^9$ 的值域不允许开数组，$1000$ 的元素数又让哈希表极小。这是「离散化」最轻量的形态，遇到「值很大但个数很少」的输入立刻想到它。

计数题的乘法结果要用 64 位承接并立即取模。两个已取模的数相乘可达 $10^{18}$，32 位整型必然溢出。习惯性地把 $dp$ 声明成 64 位、乘完立刻取模，能消除一整类隐蔽的错误。

面试视角：这题的关键陈述是「以某个值为根的树的数量，只取决于这个值」。说出来之后，状态定义、排序保证拓扑序、哈希表查另一半因子这三步会自然展开。常见追问有两个：一是「左右子树要不要区分」，要能给出 10(2,5) 与 10(5,2) 这个具体例子；二是「能不能优化到 $O(n \sqrt{V})$」，正确回答是不能——$V$ 到 $10^9$ 时 $\sqrt{V}$ 远大于 $n$，枚举数组里的候选反而更快，这体现你会根据约束选择枚举维度。能主动指出「$dp$ 初值是 1 因为单节点也算一棵树」，也是很实在的细节意识。

易错点总结

错误写法：$dp$ 初始化为 0。以 arr = [2, 4] 为例，正确答案是 3（单节点 2、单节点 4、以及 4(2,2)）；初值为 0 时 $dp = [0, 0]$，内层累加 $dp[0] \times dp[0] = 0$，最终返回 0。每个值自身就是一棵合法的树，这个 1 是真实计数而非占位。

错误写法：不排序直接双层循环。以 arr = [4, 2] 为例，$i = 0$ 是 4，内层为空，$dp[0] = 1$；$i = 1$ 是 2，$4 \bmod 2$ 的方向反了，$2 \bmod 4 \ne 0$ 跳过，最终返回 2，而正确答案是 3。必须保证计算 $dp[i]$ 时因子的 $dp$ 已就绪。

错误写法：内层循环写成 j < n 并允许 $j = i$。以 arr = [2, 4] 中的 $i = 1$ 为例，$j = 1$ 时 $arr[1] \bmod arr[1] = 0$，另一因子是 $4/4 = 1$；1 不在数组里所以侥幸被哈希挡住。但若数组恰好含有值 1（本题约束下不会，迁移到其它题时会），就会把 4(4,1) 这种非法分解算进去。内层上界应严格为 $i$。

错误写法：只枚举 $a \le \sqrt{x}$ 的因子再把结果乘二。以 arr = [2, 4] 为例，$x = 4$ 时唯一分解是 $2 \times 2$，乘二会算成 2 棵，$dp[1]$ 变成 3，最终返回 4，而正确答案是 3。$a = b$ 的情形不能乘二，直接枚举有序对可以规避这个特判。

错误写法：忘记另一个因子也必须在数组中，直接用 $dp$ 的默认值 1。以 arr = [2, 6] 为例，$6 \bmod 2 = 0$，另一因子是 3 但 3 不在数组里，这个分解非法；若不查哈希表就按 $dp[j] \times 1$ 累加，$dp[1]$ 变成 2，返回 3，而正确答案是 2。两个孩子的值都必须是数组中的元素。

错误写法：$dp$ 用 32 位整型。以一个精心构造的、$dp$ 值接近 $10^9$ 的输入为例，$dp[j] \times dp[k]$ 达到 $10^{18}$，32 位整型直接溢出成负数或截断值，取模也无法还原，结果错误。$dp$ 必须用 64 位。

错误写法：只在最后求和时取模，累加过程中不取模。以 $n = 1000$ 且分解关系密集的输入为例，$dp[i]$ 在内层循环里会被累加上千次，即便用 64 位也可能在多次乘法叠加后逼近溢出；更直接的问题是 $dp$ 值超过模数后，后续以它为因子的乘积会偏离正确的同余类。每次累加后立即取模是标准做法。

错误写法：答案只取 $\max dp[i]$ 或只取 $dp[n-1]$。以 arr = [2, 4, 5, 10] 为例，$\max dp = 3$、$dp[n-1] = 3$，而正确答案是所有 $dp$ 之和 7。题目问的是树的总数，必须按根分类求和。

错误写法：认为左右子树相同的树只算一棵，于是对 $a \ne b$ 的分解只计一次。以 arr = [2, 5, 10] 为例，10(2,5) 与 10(5,2) 是两棵不同的树，只计一次会返回 4，而正确答案是 5。二叉树的左右孩子有序。

错误写法：哈希表建成「值 → dp 值」并在循环中同步更新。以任意输入为例，这看似省掉了一次下标间接寻址，但 $dp[i]$ 在内层循环中会被多次修改，若映射里存的是旧值就会算错；更糟的是当 $k = i$（不可能发生但代码上无法排除）时会读到半成品。存下标、每次现取 $dp[k]$ 才是安全的。

错误写法：用二分查找代替哈希表，但忘了数组已被排序过而在原数组上查。以 arr = [10, 2, 5] 为例，排序后是 [2, 5, 10]，若二分时用的是排序前的引用或未同步的副本，查找结果完全错乱。用哈希表能从根本上避开「查找依赖有序性」这个耦合。

错误写法：把「每个值只能用一次」当成隐含约束。以 arr = [2, 4] 为例，4(2,2) 用了两次值 2，是合法的；若限制每个值只用一次会返回 2，正确答案是 3。题目明确说每个值可以重复使用任意多次。

相似题目

题目	难度	考察点
96. 不同的二叉搜索树	中等	同样按「根是谁」划分并让左右子树数量相乘，但划分依据是下标区间而非因子分解
95. 不同的二叉搜索树 II	中等	要真正构造出所有树而不只是计数，需在递归返回时做左右子树的笛卡尔积
241. 为运算表达式设计优先级	中等	按「最后计算哪个运算符」划分，左右结果集相乘组合，是同一种分治计数骨架
368. 最大整除子集	中等	同样靠排序建立整除方向上的拓扑序，但求的是最长链而非方案数
377. 组合总和 Ⅳ	中等	元素可重复使用的顺序敏感计数，循环嵌套顺序决定了是否区分排列
39. 组合总和	中等	元素可重复使用但要求输出方案本身，用回溯而非计数 DP，可对照两者的取舍
1. 两数之和	简单	同样用哈希表把「另一半是否存在」压成 $O(1)$ 查询，是本题查因子的最简形态