[LeetCode]Unique Binary Search Trees II

很I非常类似，递归的做法非常明显。对于1-i的数，每个数k可以作为根，那么对于左子树，generate[1, k - 1]的所有可能，对于右子树，generate[k + 1, i]的所有可能，然后分别和root连上即可。代码如下：

	/**
	* 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*> generateTrees(int n) {
	if(!n)return {};
	return backtrack(1, n);
	}
	private:
	vector<TreeNode*> backtrack(int lo, int hi)
	{
	vector<TreeNode*> res;
	if(lo > hi)return {nullptr};
	if(lo == hi)return {new TreeNode(lo)};
	for(int i = lo; i <= hi; ++i)
	{
	auto left = backtrack(lo, i - 1);
	auto right = backtrack(i + 1, hi);
	for(auto l : left)
	{
	for(auto r : right)
	{
	TreeNode* root = new TreeNode(i);
	root->left = l;
	root->right = r;
	res.push_back(root);
	}
	}
	}
	return res;
	}
	};

view raw Unique Binary Search Trees II_1.cpp hosted with ❤ by GitHub

当然递归的方法包含了太多的重复计算，我们可以用DP来优化，DP[i]存[1, i]组成的所有BST的可能。如果我们找左子树的所有可能，直接去DP数组取即可。如果是右子树，比如[m, n]的所有BST可能，我们只要把[1, n - m + 1]的所有结果向右平移然后clone新的BST出来即可。T(n) = T(0)T(n - 1) + T(1)T(n - 2) + ... +T(n - 1)T(0)，时间复杂度为Catalan Number，C(n) = (2n)!/((n + 1)!n!) 。空间复杂度的话，虽然我们不clone左子树，但是我们每次还是要给右子树分配额外的空间，用C(i)表示Catalan Number的第i个数，空间复杂度为C(1) + C(2) + ... + C(n) = O(C(n))。代码如下：

	/**
	* 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*> generateTrees(int n) {
	if(!n)return {};
	vector<vector<TreeNode*>> dp(n + 1);
	dp[0] = {nullptr};
	for(int i = 1; i <= n; ++i)
	{
	for(int j = 1; j <= i; ++j)
	{
	for(auto l : dp[j - 1])
	{
	for(auto r : dp[i - j])
	{
	TreeNode* root = new TreeNode(j);
	root->left = l;
	root->right = add(r, j);
	dp[i].push_back(root);
	}
	}
	}
	}
	return dp[n];
	}
	private:
	TreeNode* add(TreeNode* root, int num)
	{
	if(!root)return nullptr;
	TreeNode* copy = new TreeNode(root->val + num);
	copy->left = add(root->left, num);
	copy->right = add(root->right, num);
	return copy;
	}
	};

view raw Unique Binary Search Trees II_2.cpp hosted with ❤ by GitHub