What is the key pattern in the Binary Trees With Factors problem?

The primary pattern is array scanning combined with hash lookups, which allows dynamic programming to efficiently count possible binary tree formations.

How does dynamic programming help in solving the Binary Trees With Factors problem?

Dynamic programming helps by storing the number of ways each integer can form a tree, making the solution more efficient by reusing previously calculated results.

Why do we need to take results modulo 10^9 + 7?

Taking results modulo 10^9 + 7 ensures that numbers do not become too large to handle, which is especially important for large input sizes.

What is the time complexity of the Binary Trees With Factors problem?

The time complexity of the optimal solution is O(n^2), where n is the number of elements in the array. This is due to the nested iteration and hash table lookups.

What are the common pitfalls in solving the Binary Trees With Factors problem?

Common pitfalls include forgetting to apply the modulo operation and inefficient handling of array scanning and hash lookups, which can lead to incorrect solutions.

#823

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

带因子的二叉树

给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。满足条件的二叉树一共有多少个？答案可能很大，返回对 10 9 + 7 取余的结果。示例 1: 输入: ar…

数组哈希表动态规划排序

题目描述

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

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

满足条件的二叉树一共有多少个？答案可能很大，返回对 10⁹ + 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⁹
arr 中的所有值 互不相同

lightbulb

解题思路

方法一：动态规划

我们可以枚举 $arr$ 中的每一个数 $a$ 作为二叉树的根节点（根节点一定最大），然后枚举枚举左子树的值 $b$ ，若 $a$ 能被 $b$ 整除，则右子树的值为 $a / b$ ，若 $a / b$ 也在 $arr$ 中，则可以构成一棵二叉树。此时，以 $a$ 为根节点的二叉树的个数为 $f(a) = f(b) \times f(a / b)$ ，其中 $f(b)$ 和 $f(a / b)$ 分别为左子树和右子树的二叉树个数。

因此，我们先将 $arr$ 排序，然后用 $f[i]$ 表示以 $arr[i]$ 为根节点的二叉树的个数，最终答案即为 $f[0] + f[1] + \cdots + f[n - 1]$ 。注意答案可能很大，需要对 $10^9 + 7$ 取模。

时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ 。其中 $n$ 为 $arr$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)
        arr.sort()
        idx = {v: i for i, v in enumerate(arr)}
        f = [1] * n
        for i, a in enumerate(arr):
            for j in range(i):
                b = arr[j]
                if a % b == 0 and (c := (a // b)) in idx:
                    f[i] = (f[i] + f[j] * f[idx[c]]) % mod
        return sum(f) % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to optimize with dynamic programming and hash table lookups.
question_mark
Understanding of modular arithmetic in large number problems.
question_mark
Clear explanation of array scanning and the trade-off between time and space complexity.

warning

常见陷阱

外企场景

error
Forgetting to use modulo 10^9 + 7 when calculating the result.
error
Inefficient solutions due to improper handling of array scanning and hash lookups.
error
Confusing non-leaf nodes' product with other types of tree structures, leading to incorrect tree construction.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modifying the problem to allow repeated elements in the array.
arrow_right_alt
Adding constraints where each node can only appear a limited number of times in the tree.
arrow_right_alt
Changing the rules such that non-leaf nodes' values must not equal the product of their children.

help

常见问题

外企场景

继续练习

#792 匹配子序列的单词数 #1048 最长字符串链 #833 字符串中的查找与替换