卓越飞翔博客
满二叉树是一种特殊类型的二叉树，其中所有父节点要么有两个子节点，要么没有子节点。在数据结构中，这些类型的树被认为是平衡且有组织的表示。完整二叉树可能具有独特的特征，其中每个父节点都是其子节点的产物。
在本文中，我们将讨论使用 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 <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 循环，从数组的最小值到最大值进行迭代，并检查具有所需属性的完整二叉树的可能数量。
