题目链接：Unique Binary Search Trees II

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

For example,

Given n = 3, your program should return all 5 unique BST’s shown below.

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

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example: 1 / \ 2 3 / 4 \ 5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

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

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

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

这是对Unique Binary Search Trees的扩展，不是返回数目，而是需要生成所有情况的二叉搜索树。

  1. 递归分治

要生成1…n的所有结构不同的二叉搜索树，可依次令根节点为1…n。假设当前根节点为i，则其左子树为1…i-1的所有结构不同的二叉搜索树，右子树为i+1…n的所有结构不同的二叉搜索树。因此，左右子树分别转化为两个子问题了，可以选择递归处理该子问题即可。

由于不同二叉搜索树的数量是卡特兰数，因此这道题的时间复杂度是卡特兰数。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution
{
public:
    vector<TreeNode *> generateTrees(int n)
    {
        return generateTrees(1, n);
    }
private:
    vector<TreeNode *> generateTrees(int l, int r)
    {
        vector<TreeNode *> v;
        
        if(l > r)
            v.push_back(NULL);
        
        for(int i = l; i <= r; ++ i)
        {
            vector<TreeNode *> vl = generateTrees(l, i - 1);
            vector<TreeNode *> vr = generateTrees(i + 1, r);
            for(int j = 0; j < vl.size(); ++ j)
                for(int k = 0; k < vr.size(); ++ k)
                {
                    TreeNode *t = new TreeNode(i);
                    t -> left = vl[j];
                    t -> right = vr[k];
                    v.push_back(t);
                }
        }
        
        return v;
    }
};

  1. 动态规划

由于问题可以转化为子问题进行求解，因此可以选择记录已求解的子问题。记录存储的时候，为了降低空间复杂度，不采用dp[i][j]来存储i…j的所有情况，而采用dp[len]存储长度为len的所有情况，即1…len的所有情况。这样，在需要i+1…r的子问题解的情况时，需要对1…r-i的节点数值加上偏移i即可，即对dp[r-i]的所有情况加上偏移i。TreeNode * clone(TreeNode *root, int offset)函数的功能就是对root树中节点的数值进行加上偏移offset处理。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution
{
public:
    vector<TreeNode *> generateTrees(int n)
    {
        // dp[i]存储1...i的二叉搜索树
        vector<vector<TreeNode *> > dp(n + 1);
        dp[0].push_back(NULL);
        
        for(int len = 1; len <= n; ++ len)
            for(int i = 1; i <= len; ++ i)
                for(int l = 0; l < dp[i - 1].size(); ++ l)
                    for(int r = 0; r < dp[len - i].size(); ++ r)
                    {
                        TreeNode *p = new TreeNode(i);
                        p -> left = dp[i - 1][l];
                        p -> right = clone(dp[len - i][r], i);
                        dp[len].push_back(p);
                    }
        
        return dp[n];
    }
private:
    TreeNode * clone(TreeNode *root, int offset)
    {
        if(root == NULL)
            return NULL;
        
        TreeNode *p = new TreeNode(root -> val + offset);
        p -> left = clone(root -> left, offset);
        p -> right = clone(root -> right, offset);
        return p;
    }
};