leetcode

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

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    std::vector<TreeNode *> generateTrees(int n) {
        return dfs(0,n-1);
    }
private:
	std::vector<TreeNode *> dfs(int n, int m)
	{
		std::vector<TreeNode *> res;
		if(n > m)
		{
			res.push_back(NULL);
			return res;
		}
		for (int i = n; i <= m; i++)
		{
			std::vector<TreeNode *> left = dfs(n,i-1);
			std::vector<TreeNode *> right= dfs(i+1,m);
			for (int j = 0; j < left.size(); j++)
			{
				for (int k = 0; k < right.size(); k++)
				{
					TreeNode *node = new TreeNode(i+1);
					res.push_back(node);
					node->left = left[j];
					node->right= right[k];
				}
			}
		}
		return res;
	}
};