leetcode之Unique Binary Search Trees && Unique Binary Search Trees II

Unique Binary Search Trees  的原题如下：

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,

Given n = 3, there are a total of 5 unique BST's.

1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3      

思路：这道题的求解方法是卡特兰数，关于卡特兰数的介绍见此链接： http://buptdtt.blog.51cto.com/2369962/832586

这道题之所以能够利用卡特兰数求解，是因为根据根节点的不同（共有n个选择），其左右子树的个数是不同的，即在选定根节点后其树的个数是左右两个子树的乘积，刚好符合卡特兰数的计算公式。

class Solution {
public:
    int numTrees(int n) {
        vector<int> v;
		v.push_back(1);
		v.push_back(1);
		for (int i = 2; i <= n; i++)
		{
			int sum = 0;
			for(int j = 0;j< i;j++){
				sum += v[j] * v[i-j-1];
			}
			v.push_back(sum);
		}
		return v[n];
        
    }
};
           

另外，此题与n个节点所组成的不同情形的二叉树的个数是相同的， 关于n个数的不同二叉树个数，思路：在确定根节点后，可以按照左右子树节点的个数的不同来考虑，分别为左0右n-1，左1右n-2,。。。 假设f（0）=1，f（1） = 1，则可按照卡特兰数求解。

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      

这道题是上一题的延伸，需要求出具体的数结构并存放在树数组中（即vector中每个节点存放的是一棵树的根节点，据此根节点可以找到一个树结构），有了上一题的基础，这道题的思路就比较明确了，但在具体实现上差别很大。在此题的求解中要用到递归算法，由卡特兰数的求解公式可知，树的个数需要三重循环，第一层循环确定根节点的位置，并据此将左右子树分开，第二层和第三层分别遍历左右子树中的节点作为根节点的左右子树的根。然后依次递归，此题在实现的过程中需要注意的是递归结束的条件。

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        return generate(1,n);
    }
	vector<TreeNode *> generate(int start,int end){
		vector<TreeNode *>trees;
		if(start > end){
			trees.push_back(NULL);
			return trees;
		}
		if(start == end){
			trees.push_back(new TreeNode(start));
			return trees;
		}
		for(int i = start; i <= end; i++){
		    // TreeNode * root = new TreeNode(i);
			vector<TreeNode *> treeLeft =  generate(start,i - 1);
			vector<TreeNode *> treeRight = generate( i + 1,end);
			for(int j = 0; j < treeLeft.size(); j++){
				for(int k = 0; k < treeRight.size(); k++){
				    TreeNode * root = new TreeNode(i);
					root->left = treeLeft[j];
					root->right = treeRight[k];
					trees.push_back(root);
				}
			}
		}
		return trees;
        
    }
};
           

另外，在上述代码中，我曾将根节点的创建放在最外层循环中，但这样将会导致同样根节点的树的形状被最后一个树结构所覆盖，所以还是要放在最里层循环，即不同的树不能共用根节点。这道题感觉还是有一定难度的，因为思路是从上到下，但具体的构建过程却是从下到上，特别是每次递归都需要返回一个树数组，确实需要继续深入理解。。。