tree - 唯一二叉搜索树

Question

关闭。这个问题是off-topic .它目前不接受答案。












想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。

9年前关闭。




Improve this question




给定一组整数，找出可以从中构造出多少唯一的二叉搜索树？？？

根据我的说法，答案取决于整数集的大小。

我不确定答案..我说得对吗？？？

Answer 1

这可以通过使用动态规划来解决。

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