满二叉树的数量，其中每个节点都是其子节点的乘积

满二叉树是一种特殊类型的二叉树，其中所有父节点要么有两个子节点，要么没有子节点。在数据结构中，这些类型的树被认为是平衡且有组织的表示。完整二叉树可能具有独特的特征，其中每个父节点都是其子节点的产物。

在本文中，我们将讨论使用 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 循环，从数组的最小值到最大值进行迭代，并检查具有所需属性的完整二叉树的可能数量。

以上是满二叉树的数量，其中每个节点都是其子节点的乘积的详细内容。更多信息请关注PHP中文网其他相关文章！