题目：

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

背景知识：

二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
2. 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左、右子树也分别为二叉查找树。
4. 没有键值相等的节点（英语：no duplicate nodes）。

Anwser 1: 递归方法

思路：数字1~n 可以构成多少种二叉查找树。

从1~n中遍历选取一个点i作为树的根，则左子树的组合numTrees(left) 和右子树的组合numTrees(right)乘积即为当前根的组合数。

根据二叉查找树的定义，左子树结点个数为（i-1）,右子树为（n-i）。

AC Code:

class Solution {
public:
    int numTrees(int n) {
        //数字1~n 可以构成多少种二叉查找树
        //递归方法 从1~n中遍历选取一个点i作为树的根，则左子树的组合numTrees(left) 和右子树的组合numTrees(right)乘积即为当前根的组合数。
        //根据二叉查找树的定义，左子树结点个数为（i-1）,右子树为（n-i）

        if(n == 0 || n == 1)
        {
            return 1;
        }
        else
        {
            int ret = 0;
            for(int i = 1; i <= n; i++)                      //i代表root
            {
                ret += (numTrees(i-1)) * (numTrees(n-i));    //left * right
            }
            return ret;
        }
    }
};

思路：

分析问题，可知，假设f(n)表示1~n个结点给出时，BST‘s树的个数

f(n) = f(0) * f(n-1)     // 令1作为根，2~n右子树

       + f(1) * f(n-2)    // 令2作为根，1作为左子树，3~n右子树

       + ........

       + f(n-1)* f(0)     //令n作根，1~n-1作为左子树。

递归形式符合卡塔兰数模型。

卡塔兰数：

维护result[i]表示含有i个结点的二叉查找树的数量。然后依据上面分析的递推公式依次求出f(1), f(2),......f(n)。

Attention:

1. 初始化容器前两项，后面才能开始迭代。

        result.push_back(1);
        result.push_back(1);

2. 计算含i个结点时二叉查找树的种类数，j表示1~i中取任一结点作为根。所以计算方式同递归一样，左子树（J-1）*右子树(I-J)

3. 实现递推公式

   sum += (result[j-1] * result[i-j]);

4. 维护一个result的容器，容器最末尾的数即为所求F(N). 所以每次计算时需先重置0，迭代得到结果后再push进容器。

for(int i = 2; i <= n; i++)
        {
            int sum = 0;
            //计算含i个结点时二叉查找树的种类数，j表示1~i中取任一结点作为根。
            for(int j = 1; j <= i; j++)
            {
                sum += (result[j-1] * result[i-j]);   //左树*右树  实现递推公式
            }          
            result.push_back(sum);
        }

复杂度：每次求解i个结点的二叉查找树数量的需要一个i步的循环，总体需要n次。总时间复杂度O(1+2+3+....+n) = O(N^2)

空间需要一个容器维护，并且需要前i个的所有信息，所以是O(N)

AC Code:

class Solution {
public:
    int numTrees(int n) {
        vector<int> result;
        result.push_back(1);
        result.push_back(1);
        
        //二叉查找树种类总数是以所有结点为根的可行结果累加起来
        for(int i = 2; i <= n; i++)
        {
            int sum = 0;
            //计算含i个结点时二叉查找树的种类数，j表示1~i中取任一结点作为根。
            for(int j = 1; j <= i; j++)
            {
                sum += (result[j-1] * result[i-j]);   //左树*右树  实现递推公式
            }
            
            result.push_back(sum);
        }
        
        return result.back();
    }
};

[C++]LeetCode: 53 Unique Binary Search Trees