LeetCode Q95: 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

Solution (Divide and Conquer)

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<TreeNode*> helper(int start, int end){
	vector<TreeNode*> allTrees;
	if(start>end||end<start||start==end){
	TreeNode* root=NULL;
	if(start==end)
	root=new TreeNode(start);
	allTrees.push_back(root);
	return allTrees;
	}
	for(int i=start; i<=end; i++){
	vector<TreeNode*> ltrees=helper(start, i-1);
	vector<TreeNode*> rtrees=helper(i+1, end);
	for(int l=0; l<ltrees.size(); ++l){
	for(int r=0; r<rtrees.size(); ++r){
	TreeNode* root=new TreeNode(i);
	root->left=ltrees[l];
	root->right=rtrees[r];
	allTrees.push_back(root);
	}
	}
	}
	return allTrees;
	}
	vector<TreeNode*> generateTrees(int n) {
	vector<TreeNode*> allTrees;
	int start=1;
	int end=n;
	for(int i=1; i<=n; i++){
	vector<TreeNode*> ltrees=helper(start, i-1);
	vector<TreeNode*> rtrees=helper(i+1, end);
	for(int l=0; l<ltrees.size(); ++l){
	for(int r=0; r<rtrees.size(); ++r){
	TreeNode* root=new TreeNode(i);
	root->left=ltrees[l];
	root->right=rtrees[r];
	allTrees.push_back(root);
	}
	}
	}
	return allTrees;
	}
	};

view raw Q95UniqueBST.cpp hosted with ❤ by GitHub

Round2 solution

	class Solution {
	public:
	vector<TreeNode*> helper(int s, int e){
	vector<TreeNode*> res;
	if(s>e){
	TreeNode* tmp = NULL;
	res.push_back(tmp);
	return res;
	}
	for(int i=s; i<=e; i++){
	vector<TreeNode*> left = helper(s, i-1);
	vector<TreeNode*> right = helper(i+1, e);
	for(int l=0; l<left.size(); l++){
	for(int r=0; r<right.size(); r++){
	TreeNode* root = new TreeNode(i);
	root->left = left[l];
	root->right = right[r];
	res.push_back(root);
	}
	}
	}
	return res;
	}
	vector<TreeNode*> generateTrees(int n) {
	vector<TreeNode*> res;
	if(n==0)
	return res;
	res = helper(1, n);
	return res;
	}
	};

view raw gistfile1.txt hosted with ❤ by GitHub