满二叉树是一种特殊类型的二叉树，其中所有父节点要么有两个子节点，要么没有子节点。在数据结构中，这些类型的树被认为是平衡且有组织的表示。完整二叉树可能具有独特的特征，其中每个父节点都是其子节点的产物。
在本文中，我们将讨论使用 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 向量中。
-
首先，我们使用 INT_MAX 和 INT_MIN 常量查找数组中的最大值和最小值/b> C++ 中的标头。通过迭代for循环来更新最大值和最小值。
-
接下来，我们有一个嵌套循环，在其中从数组的最小值迭代到最大值。在此循环中，我们检查 dp 向量是否非零。
-
如果dp向量非零，那么我们从(j + j)开始对j的倍数运行另一个for循环，直到最大值价值。对于每个倍数，我们检查是否存在多个。
-
如果存在多个，那么可能的满二叉树的数量等于arr[j]的满二叉树的数量与arr[j]/k。
-
我们将当前更新的dp值模 1000000007 添加到结果中，以防止数据溢出。
示例
#include
#include
#include
#include
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 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
