0823. Binary Trees With Factors¶
题目信息¶
- 题号:
0823
- 难度:
Medium
- 主题:
二叉树、乘积关系、计数
- 原题:
- 重点:
每个非叶节点值必须等于左右孩子值的乘积;数组值可在不同节点重复使用,左右孩子交换通常形成不同的树
题目重述¶
给定由互不相同且都大于 1 的整数组成的数组 arr。构造非空二叉树,使树中每个节点的值都来自 arr;叶节点没有额外限制,每个非叶节点的值必须恰好等于其左孩子值与右孩子值的乘积。
数组中的某个值可以在一棵树的多个节点中重复使用,也可以用于多棵不同的树。二叉树区分左、右孩子,因此交换两个不同的孩子会得到另一棵树。请返回所有合法二叉树的数量,并对 10^9 + 7 取模。
1 <= arr.length <= 1000,2 <= arr[i] <= 10^9,数组元素互不相同。
自建示例¶
左右孩子顺序产生不同树:
输入:arr = [2,3,6]
输出:5
解释:三个数各自可以形成一棵单节点树;值 6 还可以以 2、3 为左右孩子,或以 3、2 为左右孩子,形成两棵不同的树,因此总数为 3 + 2 = 5。
数组只有一个值:
输入:arr = [7]
输出:1
解释:数组长度达到题目允许的最小值。7 无法由数组中两个值相乘得到,因此只能形成一棵以 7 为根的单节点树。