BST給出的數字鏈接列表

假設我有一個正數的鏈表，可以從它們中產生多少BST，提供所有節點都需要形成樹？BST給出的數字鏈接列表

相反，可以生成多少個BST，只要鏈表節點的任意數字都可以存在於這些樹中？

獎勵：可以形成多少平衡BST？任何幫助或指導，非常感謝。

2012-02-11 OckhamsRazor

好吧，所以BST的序列遍歷會導致排序的列表正確嗎？所以我認爲我們可以將qn分解爲「鏈表可以排序多少種方式」。這將是nCn + nC（n-1）+ ... + nC1，這將是第二個問題的答案。第一個qn的答案是n。第三個問題，我不完全確定。 – OckhamsRazor 2012-02-11 06:40:33

[確定給定節點的可能樹的數量]的可能重複（http://stackoverflow.com/questions/9238440/determine-number-of-possible-tree-from-given-nodes） – 2012-02-11 08:14:54

您可以使用動態編程來計算。

請注意，數字是多少並不重要。換句話說，對於任何n個不同的整數，都有相同數量的不同BST。我們稱這個數字爲f（n）。

然後，如果你知道對於k < N·（K），就可以得到F（N）：

f(n) = Sum (f(i) + f(n-1-i), i = 0,1,2,...,n-1)

各加數代表的樹木，其中（1 + i）的最小數量數字在根上（因此在左邊的子樹裏我是數字，在右邊的子樹裏有n-1-i）。所以DP解決了這個問題。

現在BSTS總數（從列表中的任何節點）僅僅是一個總和：

Sum (Binomial(n,k) * f(k), k=1,2,3,...,n)

這是因爲你可以選擇其中K的Binomial(n,k)方式，然後你知道有f(k) BST爲他們。

來源

2012-02-12 08:27:00

BST給出的數字鏈接列表

回答

相關問題