数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学满足每个节点都是其子节点乘积的完全二叉树的数量
完全二叉树是一种特殊的二叉树，其中所有父节点要么有两个子节点，要么没有子节点。在数据结构中，这类树被认为是平衡且组织良好的表示。完全二叉树可能具有一个独特的特征，即每个父节点都是其子节点的乘积。
在本文中，我们将讨论使用C++计算满足每个节点都是其子节点乘积的完全二叉树数量的不同方法。
输入输出场景
例如，在数组{1, 5, 3, 4}中，我们只有四个单节点1 (1 x 1), 5 (1 x 5), 3 (1 x 3) 和 4 (1 x 4)。
Input: arr = {1, 5, 3, 4}
Output: 4
在给定的数组中，使用每个元素的所有小于最大值的倍数，如果该倍数存在于数组中，则可以构成一个完全二叉树。因此，我们找到数组中的最大值。
我们从最小值迭代到最大值来开始查找这样的二叉树，因为我们知道较小的值可能是数组中较大值的倍数。
使用动态规划
在这里，我们使用动态规划来查找满足每个节点都是其子节点乘积的完全二叉树的数量。我们迭代数组元素并找到满足上述条件的可能的树。我们将这些解存储在dp向量中。
首先，我们使用在C++的<climits>头文件中定义的INT_MAX和INT_MIN常量来查找数组中的最大值和最小值。最大值和最小值通过迭代for循环来更新。
接下来，我们有一个嵌套循环，在其中我们从数组的最小值迭代到最大值。在这个循环中，我们检查dp向量是否为零。
如果dp向量不为零，则我们从(j + j)到最大值迭代j的倍数的另一个for循环。对于每个倍数，我们检查该倍数是否存在。
如果倍数存在，则可能的完全二叉树的数量等于arr[j]的完全二叉树的数量和arr[j]/k的完全可能的二叉树的数量的乘积。
我们将当前更新的dp值模1000000007加到结果中，以防止数据溢出。
示例
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;
int numOfFullBinaryTrees(int arr[], int N) {
int minValue = INT_MAX;
int maxValue = INT_MIN;
// Find the maximum and minimum value from the array
for (int j = 0; j < N; j++) {
minValue = min(minValue, arr[j]);
maxValue = max(maxValue, arr[j]);
}
vector < int > dp(maxValue + 1, 0);
// One possible full binary tree for each element
// in case of single nodes
for (int j = 0; j < N; j++) {
dp[arr[j]] = 1;
}
int result = 0;
for (int j = minValue; j <= maxValue; j++) {
if (dp[j] != 0) {
for (int k = j + j; k <= maxValue && (k / j) <= j; k += j) {
if (dp[k] != 0) {
dp[k] += (dp[j] * dp[k / j]);
// Check if left child may become right child and vice versa
if (j != (k / j)) {
dp[k] += (dp[j] * dp[k / j]);
}
}
}
result = (result + dp[j]) % 1000000007;
}
}
return result;
}
int main() {
int array[] = {12, 3, 5, 6};
int N = sizeof(array) / sizeof(array[0]);
cout << "Number of full binary trees satisfying the condition are: " << numOfFullBinaryTrees(array, N) << endl;
return 0;
}
输出
Number of full binary trees satisfying the condition are: 4
注意 - 此程序的时间复杂度为O(N^2)。
结论
我们讨论了如何查找满足每个节点都是其子节点乘积的完全二叉树的数量。我们使用了动态规划方法，通过将子问题的解存储在dp向量中来解决这个问题。我们可以使用简单的嵌套for循环，从数组的最小值迭代到最大值，并检查具有所需属性的完全二叉树的可能数量。
85 次浏览
