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

#include<iostream>
#include<vector>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


vector<TreeNode *>generate(int first,int last )
{
	if (first>last)
	{
		vector<TreeNode*>result(1, NULL);
		return result;
	}
	vector<TreeNode*>result;
	for (int i = first; i <= last;++i)
	{
		vector<TreeNode*> leftvector  = generate(first, i - 1);
		vector<TreeNode*> rightvector = generate(i + 1, last);
		for (int p = 0; p != leftvector.size();++p)
		{
			for (int q = 0; q != rightvector.size();++q)
			{
				TreeNode* root = new TreeNode(i);
				root->left = leftvector[p];
				root->right = rightvector[q];
				result.push_back(root);
			}
		}
	}
	return result;

}
vector<TreeNode *> generateTrees(int n) {

	return generate(1, n);
}

Unique Binary Search Trees II

原文：http://blog.csdn.net/li_chihang/article/details/44649715