唯一的二進制搜索樹

Question

給定一組整數找出有多少獨特的二進制搜索樹可以構建出來？

根據我的答案取決於整數集的大小。如果該組整數的大小是n ..然後「N」獨特的二叉搜索樹可以做出來的吧..

我不知道答案..我是嗎？

Answer 1

該數字是C_n，其中C_n是第n Catalan Number。可以遞歸地定義該值，方法是選取n個節點中的任何一個作爲根，然後採取所有可能的方法來組織根的左右子樹，導致以下遞歸關係：

C_n = sum_ {i = 0}^{N - 1} C_I * C_ {N - 1 - I}，

其中C_0 = 1

Answer 2

這可以通過使用動態編程來解決。

numTrees(i+1)=append the last node to the rightmost leaf of bst(i)[numTrees(i)] + 
       append the last node as the root of bst(i)[numTrees(i)] + 
       insert the last node as non-leaf node sum(k=1...i)(bst(k-1)*bst(i-k) 

因此它是o（n^2）解決方案。

public int numTrees(int n) { 
    if(n == 0 || n == 1 || n == 2) 
     return n; 
    int bst[] = new int[n+1]; 
    bst[0] = 1; 
    bst[1] = 1; 
    bst[2] = 2; 
    for (int i=3; i<=n; i++) { 
     for (int j=1; j<i-1; j++) { 
      bst[i] += bst[j]*bst[i-1-j]; 
     } 
     bst[i] += 2*bst[i-1]; 
    } 
    return bst[n]; 
}