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.

LeetCode问题:
给定一个数n, 能够用从1~n这n个数构造出多少个不同的Binary Tree
方法一:时间复杂度O(n^2), 空间复杂度O(n)
用DP的方法,计算n = 0,1,2… 把计算结果存在一个表中,再通过之前计算的表格计算出n的结果:
1.n=0 只能构建一个树 count[0] = 1;
2.n=1 只能构建一个树 count[1] = 1;
3.n=2 可以构建两个树 选择1作为根节点,左边子树只能为空,右边子树可以由2-1=1个元素构成。如果选择2作为根节点,左边子树也是由2-1=1个元素构成,右边子树为空。所有总的可以构成的Binary Tree的个数就可以算出来是 count[2] = count[1]*count[0] + count[0]*count[1];
4.n=3 选择1作为根节点,左边子树为空,右边子树可以由2个元素构成, 2作为根节点,左边子树可以由1个元素构成,右边子树也由一个元素构成,选择3作为根节点,左边子树可以由两个元素构成,右边子树则为空,所以计算出可以构成的Binary Tree的总数是count[3] = count[2]*count[0] + count[1]*count[1] + count[0]*count[2];

推广到n的情况,取i为根节点,左子树可以由0~i-1共i个数组成,右子树则可以由i+1 ~n共n-i-1个数组成。i可以取0~n
for i = 0 ~ n
count[n] += count[i]*count[n-i-1]

写出代码:

public class Solution {
public int numTrees(int n) {
int [] count = new int [n+1];
count[0] = 1; // 0 element, one tree
count[1] = 1; // 1 element, one tree
for (int i = 2; i < n+1; i++)
{
for (int j = 0; j < i; j++) // split 0~j, j~i j: number of elements in the left tree, range 0:i-1
count[i] += count[j] * count[i-j-1];
}
return count[n];
}
}

方法2:数学方法(没太看懂)
http://www.geeksforgeeks.org/g-fact-18/
http://en.wikipedia.org/wiki/Catalan_number
这个问题可以简化为求key个数为n的不同的Binary Tree的个数,这个数就是Catalan number
count(n)=Combination(2n, n)-Combination(2n, n+1)=(2n)!/((n+1)!n!)=(2n*(2n-1)*(2n-2)*…*(n+1))/(n+1)!
写出代码是:

public class Solution {
    public int numTrees(int n) {
        if (n == 0 || n == 1)
            return 1;
        else
        {
            double count = 1; // because we use divde below, use float or double
            for (double i = 2; i <= n+1; i++) // only apply to i = 2, if i = 1, the catalan formula does not hold
            {
                count = count * (((double)n+i-1)/i);
            }
            return (int)Math.round(count); // use round method to round correctly (casting will always round down)
        }
    }
}  

注意做除法时需要用double而不能用int,另外round结果是不能只用casting,而要用math.round,不然casting只是舍弃所有的小数位而不是四舍五入。

Second submission:

Pay attention to the split, use dp

public class Solution {
    public int numTrees(int n) {
        int [] count = new int [n+1];
        count[0] = 1;
        count[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {//j: number of element on the left
                count[i] += count[j] * count[i-j-1];
            }
        }
        return count[n];
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s