Unique Binary Search Tree

Oct 22, 2017

第29天。

今天的题目是Unique Binary Search Trees:

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example, Given n = 3, there are a total of 5 unique BST’s.

1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3

对于这种问题一般都可以用递归去做的,我们尝试的找一下递归式。

n=1 -> 1 n=2 -> 2 n=3 -> 5

我们考虑n=3时的情况,这时这棵树种包含三个值1,2,3,这说明树根的可能是1,2,3中的一个值:

  • root=1时,2,3只能放在右子树。现在只考虑2,3两个值,由于BST的性质,右子树也必须是BST,则此时问题转换成求numsTrees(2).
  • root=2时,左边必定是1,右边必定是3.
  • root=3时,左边必定是1,2,同样转换成numsTrees(2).

我们再考虑一下n=5时的情况:

  • root=3,左子树必定是是包含1,2的BST,右子树必定是包含4,5的BST,此时种类为numsTree(5-3)*numsTrees(3-1)

所以我们可以找到递推式:

  • n < 2 -> numsTrees(n) = 1
  • n >= 2 -> numsTrees(n) = numsTrees(1)*numsTrees(n-1) + numsTrees(2)*numTree(n-2) + ... + numsTree(n-1)*numsTrees(1);

所以我们写出一个递归的解决方案:

int numTrees(int n) {
    if (n <= 1) return 1;

    int ret = 0;
    for(int i = 1;i <= n;i++) {
        int left = i-1;
        int right = n-i;
        ret += numTrees(left)*numTrees(right);
    }
    return ret;
}

但是这里会超时,很明显这里可以用动态规划来优化:

int numTrees(int n) {
    vector<int> ret(n+1);
    ret[0] = 1;
    ret[1] = 1;
    for(int i = 2;i <= n;i++) {
        for(int j = 1;j <= i;j++)
            ret[i] += ret[j-1]*ret[i-j];
    }
    return ret[n];
}

dicuss中基本都是和上面类似的解法,除了一个:

int numTrees(int n) {
    //cantalan树
    //C(2n,n)/(n+1)
    long long ans =1;
    for(int i=n+1;i<=2*n;i++){
        ans = ans*i/(i-n);
    }
    return ans/(n+1);
}

emmm,说实话,我没看懂,但是这个方法的确是最快的,只需要O(n)的时间,O(1)的空间。

LeetCodeLeetCode动态规划

Validate Binary Search Tree

Word Search

comments powered by Disqus