95. Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

---

本题在LeetCode Unique Binary Search Trees的基础上，要求给出具体有哪些不同的二叉搜索树。方法是一样的DP，先枚举根节点r，然后把[1,n]分成两个部分，[1,…,r-1]递归的生成左子树，[r+1,…,n]递归的生成右子树。然后把左右子树接到r的左右两边。完整代码如下：

class Solution {
public:
    vector<TreeNode*> generate(int start, int end)
    {
        if (start > end)
            return vector<TreeNode*>({ NULL });
        if (start == end)
            return vector<TreeNode*>({ new TreeNode(start) });
        vector<TreeNode*> ans;
        for (int root = start; root <= end; ++root) {
            //TreeNode* rt = new TreeNode(root); //注意根节点不能放在这里，不能共用
            vector<TreeNode*> left = generate(start, root – 1);
            vector<TreeNode*> right = generate(root + 1, end);
            for (int l = 0; l < left.size(); ++l) {
                for (int r = 0; r < right.size(); ++r) {
                    TreeNode* rt = new TreeNode(root); //每棵树的根节点是独立的，要不然下一轮修改会影响上一轮结果
                    rt->left = left[l];
                    rt->right = right[r];
                    ans.push_back(rt);
                }
            }
        }
        return ans;
    }
    vector<TreeNode*> generateTrees(int n)
    {
        if (n < 1)
            return vector<TreeNode*>();
        return generate(1, n);
    }
};

本代码提交AC，用时26MS。