该题的第一版本，我几乎没有抓住问题的本质，而是纠结于卡特兰数的公式。见[06. Unique Binary Search Trees](../06. Unique Binary Search Trees)

无论怎么说，我们对 BST 应该非常清晰的认识，我总结三句话描述它的特点：

左小右大
递归向下
独一无二

第一个特点说的是，左子树若存在，则其所有节点值均小于根节点；而右子树若存在，则其所有节点值均大于根节点。

第二个特点指，该结构具备递归性，其左、右节点也皆为 BST

第三个特点指，no duplicate nodes. 不存在值相等的节点。

我们熟知的 std::map 和 std::set 一般实现为红黑树，而红黑树恰是 BST 的一种（优化版）。

说完概念与本质，再来分析题意。参数是节点数，要求用 1 ~ n 来组建所有可能的 BST。

根据第一个特点，1 ~ n 每一个值都可以用来做根节点，所以应该有一次循环：for(int i=1; i<n; ++i)
根据第二个特点，可以递归的解决左、右子树。
无需考虑等于的情况。

结合以上三点，基本的思路就有了。1 ~ n个节点，若 m 为根节点，那么：

左子树 : 1 ~ m-1
右子树 : m+1 ~ n

但由于循环的需要，而我们的根又是从 1 开始的，于是可以将上述范围改为：

左子树 : 1 ~ m
右子树 : m+1 ~ n+1

可以看出是一个 [) 的区间。

而这种形式也决定了咱们递归函数的格式：

vector<TreeNode *> generateTrees(int b, int e) // 起点与终点(终点不被包括)
{
    if (e-b<2) return vector<TreeNode *>{e-b ? new TreeNode(b) : NULL}; // 如果起点==终点，证明该树为空；如果仅有起点存在，则返回起点数组。
    vector<TreeNode *> retv; // 最终返回的 vector
    for (int i=b; i<e; ++i) // 迭代每一个可以成为根节点的值
    {
        vector<TreeNode *> retLeft = generateTrees(b, i); // 递归计算左子树
        vector<TreeNode *> retRight = generateTrees(i+1, e); // 递归计算右子树

        // 迭代拼接根节点与左子树右子树
        for (auto pL : retLeft)
            for (auto pR : retRight) {
                TreeNode *root = new TreeNode(i); // new 出根
                root->left = pL;
                root->right = pR;
                retv.push_back(root); // 存入 vector.
            }
    }
}

效率还不错，排名靠前。84ms.