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。

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3
Output: 5
Explanation:
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

---

给定n，问保存1~n的二叉搜索树共有多少种形式。注意要充分利用二叉搜索树的特点，左孩子小于等于根节点，根节点小于等于右孩子。如果trees[0,…,n-1]保存了0,…,n-1个节点的二叉搜索树的个数，现在要求trees[n]。n个节点，除了根节点，剩余n-1个节点，根据选取的根节点的不同，把n-1个节点分在了不同的左右子树中，以该节点为根的有效的二叉搜索树个数等于左右孩子有效的二叉搜索树个数乘积。
以3个点为例，如下图所示，如果选取1作为根节点，则左右孩子的节点数分别为0,2，所以可以有的二叉搜索树形式为trees[0]*trees[2]；如果选取2作为根节点，则左右孩子的节点数分别为1,1，所以可以有的二叉搜索树形式为trees[1]*trees[1]；同理3为trees[2]*trees[0]。

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

所以trees[n]=trees[0]*trees[n-1]+trees[1]*trees[n-2]+…+trees[n-1]*trees[1]。这其实就是卡特兰数：

完整代码如下：

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

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