LeetCode 823. 带因子的二叉树

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 腾讯
标签
数组 哈希表 动态规划 排序

题目描述

✅ 823. 带因子的二叉树

image-20260929104849272

题意分析

数组中的数互不相同且都大于 1，每个数可以被重复用作任意多个节点。构造二叉树时，每个非叶节点的值必须等于左右孩子值的乘积，求不同二叉树的总数，对 10^9 + 7 取模；左右子树的位置需要区分。

解法：排序 + 按根值动态规划

核心思路

[!blue]

按根节点值分类，令 dp[i] 表示以 arr[i] 为根的树的数量。每个值都能单独形成叶子节点，所以状态初值为 1；非叶树再按左右孩子的根值分类累加。

先将数组升序排序。由于两个因子都大于 1，任何合法孩子值都严格小于根值，因此计算 dp[i] 时，左右子树所需状态已经算好。枚举 j < i 作为左孩子，只有 arr[j] 整除根值时才继续，并用哈希表查找右孩子值 arr[i] / arr[j] 是否存在。

若右孩子对应下标 k，左子树有 dp[j] 种选择，右子树有 dp[k] 种选择，两侧独立，因此贡献 dp[j] * dp[k]。每棵非叶树都有唯一的左右根值和左右子树组合，所以这些分类既不漏算，也不重复。

左右根值不同时，枚举左因子会分别遇到两个方向，已经计入镜像次序；两值相同时只枚举一次，但左右子树形状仍可独立选择，平方本身已覆盖所有有序组合，不能再额外乘二。数组值可重复使用，因此不需要从可用集合中移除孩子值。

每次贡献相乘后累加并取模，乘法使用宽整数，避免在取模之前溢出。最终根节点可以取数组中任意值，所以答案是所有 dp[i] 的和，而不是最后一个状态。

解题步骤

  1. 排序并建立数值到下标的映射。
  2. 所有根状态初始化为一。
  3. 逐根枚举小于当前根值的左因子，右因子存在则累加子树方案数乘积。
  4. 每次累加取模，最终求全部根状态之和。

代码实现

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

import "sort"

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)$，状态数组和数值索引；排序会修改输入数组。

关键点总结

[!green]

  • 初值一计入每个数单独成树的情况。
  • 有序因子枚举自动处理镜像与相同孩子。
  • 乘法先在宽整数中完成，再取模。

易错点总结

[!yellow]

  • 状态初始化为零：所有单节点树都被漏掉。
  • 只检查整除，不检查另一因子存在：可能使用数组中没有的节点值。
  • 所有因子对统一乘二：两个孩子值相同时会多算。
  • 只返回最大根的状态：遗漏其他根值对应的树。

相似题目

题目 难度 关联与区别
96. 不同的二叉搜索树 中等 同样把左右子树方案数相乘再累加，本题左右根还必须满足因子乘积等于当前根值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/38614771
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！