資料結構
網路
關係資料庫管理系統 (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 次瀏覽
