唯一的二进制搜索树

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]; 
}