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;
        
    }
};
           

另外，在上述代碼中，我曾将根節點的建立放在最外層循環中，但這樣将會導緻同樣根節點的樹的形狀被最後一個樹結構所覆寫，是以還是要放在最裡層循環，即不同的樹不能共用根節點。這道題感覺還是有一定難度的，因為思路是從上到下，但具體的建構過程卻是從下到上，特别是每次遞歸都需要傳回一個樹數組，确實需要繼續深入了解。。。