0823-带因子的二叉树

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给出一个含有不重复整数元素的数组 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 中的所有值 互不相同

方法一：动态规划 + 双指针

因为每个整数 arr}[i] 均大于 1，因此每个非叶结点的值都大于它的子结点的值。考虑以 arr}[i] 为根结点的带因子的二叉树，那么它的所有子孙结点的值都小于 arr}[i]。我们将 arr 从小到大进行排序，那么对于以 arr}[i] 为根结点的带因子的二叉树，它的子孙结点值的下标只能在区间 [0, i - 1) 中。
使用 dp}[i] 保存以 arr}[i] 为根结点的带因子的二叉树数目。我们从区间 [0, i - 1) 内枚举 arr}[i] 的子结点，假设存在 0 \le \textit{left} \le \textit{right} \lt i，使 arr}[\textit{left}] \times \textit{arr}[\textit{right}] = \textit{arr}[i] 成立，那么 arr}[\textit{left}] 和 arr}[\textit{right}] 可以作为 arr}[i] 的两个子结点。同时 arr}[\textit{left}] 和 arr}[\textit{right}] 为根结点的带因子二叉树数目分别为 dp}[\textit{left}] 和 dp}[\textit{right}]，不难推导出 arr}[\textit{left}] 和 arr}[\textit{right}] 作为 arr}[i] 的两个子结点时，带因子二叉树数目 s 为：

  • left} = \textit{right 时，s = \textit{dp}[\textit{left}] \times \textit{dp}[\textit{right}]

  • left} \ne \textit{right 时，因为两个子结点可以交换，所以 s = \textit{dp}[\textit{left}] \times \textit{dp}[\textit{right}] \times 2

当 arr}[i] 没有子结点时，对应 1 个带因子二叉树。因此，状态转移方程为：

\textit{dp}[i] = 1 + \sum_{(\textit{left}, \textit{right}) \in U} \textit{dp}[\textit{left}] \times \textit{dp}[\textit{right}] \times (1 + f(\textit{left}, \textit{right}))

其中 (\textit{left}, \textit{right}) \in U 表示所有满足 0 \le \textit{left} \le \textit{right} \lt i 且 arr}[\textit{left}] \times \textit{arr}[\textit{right}] = \textit{arr}[i] 的下标对 (\textit{left}, \textit{right})，而 f(\textit{left}, \textit{right}) 的取值为当 left} = \textit{right 时，值为 0，否则值为 1（因为 left} \ne \textit{right 时，两个子结点可以交换）。

找出 (\textit{left}, \textit{right}) \in U 的所有 (\textit{left}, \textit{right}) 可以使用双指针进行查找。

[sol1-C++]
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
class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        vector<long long> dp(n);
        long long res = 0, mod = 1e9 + 7;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int left = 0, right = i - 1; left <= right; left++) {
                while (right >= left && (long long)arr[left] * arr[right] > arr[i]) {
                    right--;
                }
                if (right >= left && (long long)arr[left] * arr[right] == arr[i]) {
                    if (right != left) {
                        dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod;
                    } else {
                        dp[i] = (dp[i] + dp[left] * dp[right]) % mod;
                    }
                }
            }
            res = (res + dp[i]) % mod;
        }
        return res;
    }
};
[sol1-Java]
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
class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        long[] dp = new long[n];
        long res = 0, mod = 1000000007;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int left = 0, right = i - 1; left <= right; left++) {
                while (right >= left && (long) arr[left] * arr[right] > arr[i]) {
                    right--;
                }
                if (right >= left && (long) arr[left] * arr[right] == arr[i]) {
                    if (right != left) {
                        dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod;
                    } else {
                        dp[i] = (dp[i] + dp[left] * dp[right]) % mod;
                    }
                }
            }
            res = (res + dp[i]) % mod;
        }
        return (int) res;
    }
}
[sol1-C#]
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
public class Solution {
    public int NumFactoredBinaryTrees(int[] arr) {
        Array.Sort(arr);
        int n = arr.Length;
        long[] dp = new long[n];
        long res = 0, mod = 1000000007;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int left = 0, right = i - 1; left <= right; left++) {
                while (right >= left && (long) arr[left] * arr[right] > arr[i]) {
                    right--;
                }
                if (right >= left && (long) arr[left] * arr[right] == arr[i]) {
                    if (right != left) {
                        dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod;
                    } else {
                        dp[i] = (dp[i] + dp[left] * dp[right]) % mod;
                    }
                }
            }
            res = (res + dp[i]) % mod;
        }
        return (int) res;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func numFactoredBinaryTrees(arr []int) int {
    sort.Ints(arr)
    dp := make([]int64, len(arr))
    res, mod := int64(0), int64(1e9 + 7)
    for i := 0; i < len(arr); i++ {
        dp[i] = 1
        for left, right := 0, i - 1; left <= right; left++ {
            for left <= right && int64(arr[left]) * int64(arr[right]) > int64(arr[i]) {
                right--
            }
            if left <= right && int64(arr[left]) * int64(arr[right]) == int64(arr[i]) {
                if left == right {
                    dp[i] = (dp[i] + dp[left] * dp[right]) % mod
                } else {
                    dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod
                }
            }
        }
        res = (res + dp[i]) % mod
    }
    return int(res)
}
[sol1-C]
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
int cmp(const void *p1, const void *p2) {
    return *(int *)p1 - *(int *)p2;
}

int numFactoredBinaryTrees(int *arr, int arrSize){
    qsort(arr, arrSize, sizeof(int), cmp);
    long long *dp = (long long *)malloc(arrSize * sizeof(long long));
    long long res = 0, mod = 1e9 + 7;
    for (int i = 0; i < arrSize; i++) {
        dp[i] = 1;
        for (int left = 0, right = i - 1; left <= right; left++) {
            while (left <= right && (long long)arr[left] * arr[right] > arr[i]) {
                right--;
            }
            if (left <= right && (long long)arr[left] * arr[right] == arr[i]) {
                if (left == right) {
                    dp[i] = (dp[i] + dp[left] * dp[right]) % mod;
                } else {
                    dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod;
                }
            }
        }
        res = (res + dp[i]) % mod;
    }
    return res;
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        n = len(arr)
        arr = sorted(arr)
        dp = [1] * n
        res, mod = 0, 10**9 + 7
        for i in range(n):
            left, right = 0, i - 1
            while left <= right:
                while right >= left and arr[left] * arr[right] > arr[i]:
                    right -= 1
                if right >= left and arr[left] * arr[right] == arr[i]:
                    if right != left:
                        dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod
                    else:
                        dp[i] = (dp[i] + dp[left] * dp[right]) % mod
                left += 1
            res = (res + dp[i]) % mod
        return res
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var numFactoredBinaryTrees = function(arr) {
    const n = arr.length;
    const mod = 1e9 + 7;
    const dp = new Array(n).fill(1)
    arr.sort((a, b) => a - b);
    let res = 0;
    for (let i = 0; i < n; i++) {
        for (let left = 0, right = i - 1; left <= right; left++) {
            while (right >= left && arr[left] * arr[right] > arr[i]) {
                right--;
            }
            if (right >= left && arr[left] * arr[right] == arr[i]) {
                if (right != left) {
                    dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod;
                } else {
                    dp[i] = (dp[i] + dp[left] * dp[right]) % mod;
                }
            }
        }
        res = (res + dp[i]) % mod;
    }
    return res;
};

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 是数组 arr 的长度。双指针找两个子结点需要 O(n)，总时间复杂度为 O(n^2)。

  • 空间复杂度：O(n)。保存动态规划的状态需要 O(n)。

 Comments
On this page
0823-带因子的二叉树