P149 二叉搜索树的数量

描述#

这个题目说的是，给你一个整数 n，你要计算出，由 1 ~ n 这 n 个数字可以构成多少棵不同的二叉搜索树。

比如说，给你的 n 是 3，1/2/3 这 3 个数字总共可以构成 5 棵不同的二叉搜索树。如下所示：
1     1     2     3     3
\     \   / \   /     /
2     3 1   3 1     2
\   /         \   /
3 2           2 1
因此，你要返回的数量就是 5。

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(n)
  public int numTreesDP(int n) {
    if (n < 0) return 0;
    int[] d = new int[n+1];
    d[0] = 1;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= i; ++j)
        d[i] += d[j-1] * d[i-j];
    return d[n];
  }

  // Time: O(n), Space: O(1)
  public int numTreesMath(int n) {
    if (n < 0) return 0;
    long result = 1;
    for (int k = 1; k <= n; ++k)
      result = result * (n + k) / k;
    return (int)(result / (n+1));
  }

}