Unique Binary Tree II@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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.

这道题我觉得很难，思路我有，就是左右子树递归填值，基本的idea 就是 

node->val=i;

buildTree(node->left, l, i-1);

buildTree(node->right, i+1, r);

但问题是，我们要存的是一系列的子树，就是说一个n，它左右两边会有很多种类型的子树，它要全部都连接上，并且存到vector里面。这样逻辑就很难想明白（对于我这种recursion没有炉火纯青滴娃）。而且这里要用值传递，比较不浪费空间，不然都用指针，都在栈里面开辟空间，没调用一次都得开一堆东西，太麻烦。

我自己没想出来，参考了别人的答案。这个题可以让我们好好学习recursion。

后一个code用指针，因为涉及太多的vector数列，会需要用到很多拷贝构造，而且变量在栈上开辟。所以我们用指针来做。面试的时候注意。

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	void buildTrees(vector<TreeNode *> &res, int l, int r)
	{
	if(l>r)
	{
	res.push_back(NULL);
	return;
	}
	else
	{
	for(int i=l; i<=r; i++)
	{
	vector<TreeNode *> left;
	buildTrees(left,l,i-1);
	vector<TreeNode *> right;
	buildTrees(right,i+1,r);
	for(int li=0; li<left.size(); li++)
	{
	for(int ri=0; ri<right.size(); ri++)
	{
	TreeNode *node= new TreeNode(i);
	node->left=left[li];
	node->right=right[ri];
	res.push_back(node);
	}
	}
	}
	}
	}
	vector<TreeNode *> generateTrees(int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<TreeNode *> res;
	buildTrees(res, 1, n);
	return res;
	}
	};

view raw Unique Binary Tree II hosted with ❤ by GitHub

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<TreeNode *>* generate(int start, int end)
	{
	vector<TreeNode *> *subTree = new vector<TreeNode*>();
	if(start>end)
	{
	subTree->push_back(NULL);
	return subTree;
	}
	for(int i =start; i<=end; i++)
	{
	vector<TreeNode*> *leftSubs = generate(start, i-1);
	vector<TreeNode*> *rightSubs = generate(i+1, end);
	for(int j = 0; j< leftSubs->size(); j++)
	{
	for(int k=0; k<rightSubs->size(); k++)
	{
	TreeNode *node = new TreeNode(i);
	node->left = (*leftSubs)[j];
	node->right = (*rightSubs)[k];
	subTree->push_back(node);
	}
	}
	}
	return subTree;
	}
	vector<TreeNode *> generateTrees(int n) {
	if(n ==0) return *generate(1,0);
	return *generate(1, n);
	}
	};

view raw UniqueBinaryTreeII hosted with ❤ by GitHub