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给定一个序列1~n，为了构造二叉树，我们可以使用1~n中的第 i 个节点作为根节点，则根据二叉排序树的性质，1~n-1必在左子树，n+1~n在右子树；
f(0)= 1； f(1) = 1； f(2) = f(1) * f(0) + f(0) * f(1)； 以第 i 个节点作为根节点有f(i - 1) * f( n - 1 - i)中二叉排序树的可能； 则f(n) = f(0) * f(n - 1) + f(1) * f(n-2)+…+f(n-1) * f(0)
思路1：用一个二重循环
int numTrees(int n) { if (n == 0)return 0; if (n == 1)return 1; vector<int> res(n + 1, 0); res[0] = 1, res[1] = 1; for (int i = 2; i <= n; i++){ for (int j = 1; j <= i; j++){ res[i] += res[j - 1] * res[i - j]; } } return res[n]; }思路2：递归
int numTrees(int n) { if (n == 0 || n == 1)return 1; int res = 0; for (int i = 0; i < n; i++){ res += numTrees(i) * numTrees(n - i - 1); } return res; }思路3：数学公式直接求解
int numTrees(int n) { if (n == 0)return 0; if (n == 1)return 1; vector<long>res(n + 1, 0); res[0] = 1, res[1] = 1; for (int i = 1; i < n; i++){ res[i + 1] = 2 * (2 * i + 1) *res[i] / (i + 2); } return res[n]; }