学步园

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.

思想十分难，程序构造处理并不复杂。

//2014-2-15 update AC
	vector<TreeNode *> generateTrees(int n) 
	{
		return gen(1, n);
	}
	vector<TreeNode *> gen(int left, int right)
	{
		if (left > right) return vector<TreeNode *>(1, nullptr);
		vector<TreeNode *> rs;

		for (int k = left; k <= right; k++)
		{
			vector<TreeNode *> lt = gen(left, k-1);
			vector<TreeNode *> rt = gen(k+1, right);

			for (int i = 0; i < lt.size(); i++)
			{
				for (int j = 0; j < rt.size(); j++)
				{
					TreeNode *n = new TreeNode(k);
					n->left = lt[i];
					n->right = rt[j];
					rs.push_back(n);
				}
			}
		}
		return rs;
	}