题目链接：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

这道题的要求是求用1…n生成结构不同的二叉搜索树（BST）的数量。

二叉搜索树，顾名思义，它是一个二叉树，即每个节点下面最多有2个子节点。同时为了便于搜索的特性，二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：

  • 若其左子树不空，则左子树上所有结点的值均小于根结点的值；
  • 若其右子树不空，则右子树上所有结点的值均大于根结点的值；
  • 其左、右子树也分别为二叉搜索树。

1…n的所有结构不同的二叉搜索树的数量，可以注意到这是一个卡特兰数。

  1. 递归分治

生成二叉搜索树，可以选取1…n中的任意节点i当根节点，然后比i小的放到左子树，比i大的放到右子树即可。因此i需要遍历1…n，然后累加每次情况。其中每次左子树有i-1个点，右子树有n-i个点，左右子树的数量需要递归处理，再相乘即为根节点是i情况下不同二叉搜索树的数量。

时间复杂度：O(???)

空间复杂度：O(???)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution
{
public:
    int numTrees(int n)
    {
        if(n == 0 || n == 1)
            return 1;
        
        int sum = 0;
        for(int i = 1; i <= n; ++ i)
            sum += numTrees(i - 1) * numTrees(n - i);
        return sum;
    }
};

  1. 动态规划

动态规划的思路就是记录上面递归处理子问题的解即可。

时间复杂度：O(n^2)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution
{
public:
    int numTrees(int n)
    {
        vector<int> dp(n + 1, 0);
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= n; ++ i)
            for(int j = 1; j <= i; ++ j)
                dp[i] += dp[j - 1] * dp[i - j];
        return dp[n];
    }
};

  1. 卡特兰数

由于该问题是卡特兰数，因此可以选择计算卡特兰数的方案处理该问题。

  1. h(n)= h(0)h(n-1)+h(1)h(n-2) + … + h(n-1)h(0) (n>=2)
  2. h(n)=h(n-1)(4n-2)/(n+1) (n>=1)
  3. h(n)=C(2n,n)/(n+1) (n=0,1,2,…)
  4. h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,…)

利用第3个公式即可。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11

class Solution
{
public:
    int numTrees(int n)
    {
        int h = 1;
        for(int i = 2; i <= n; ++ i)
            h = h * (4 * i - 2) / (i + 1);
        return h;
    }
};