leetCode(26):Unique Binary Search Trees

Givenn, how many structurally uniqueBST’s(binary search trees) that store values 1…n?

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

13321\/// \\3211 32//\\ 21231）结构的总数和存储的n个有序数没有关系，即存放的是1,2,3或5、6、9结果都是一样的；2）n=0\1时，结果都为1；n个有序数，取任何一个作为根结点，该值左边的为左子树，右边的为右子树，在这种情况下，可能的结构总数为：左子树结构数*右子树结构数，所以原问题就被分解成了两个子问题；3）将取n个有序数作为根结点的情况的结构问题相加，即可得到原问题的解，，但应注意的是，如：1、2、3取1或3作为根结点的情况，结构数是相同的，即具有对称性；那么也要考虑到奇偶性；4）能够被分解成相同的子问题，自己就可以采用递归，本程序采用循环的方法。*/ int numTrees(int n){vector<int> store;store.push_back(1);store.push_back(1);for(int i=2;i<=n;++i){int tmp=0;for(int j=0;j<i/2;++j){tmp+=2*store[i-1-j]*store[j];}if(i%2)tmp+=store[i/2]*store[i/2];store.push_back(tmp);}return store[n];}

在前进的路上，主动搬开别人脚下的绊脚石，有时往往也是为自己铺路。