滿二叉樹的數量，其中每個節點都是其子節點的乘積

滿二叉樹是一種特殊類型的二元樹，其中所有父節點要麼有兩個子節點，要麼沒有子節點。在資料結構中，這些類型的樹被認為是平衡且有組織的表示。完整二元樹可能具有獨特的特徵，其中每個父節點都是其子節點的產物。

在本文中，我們將討論使用 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中文網其他相關文章！