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
分析：本题非常easy想到用递归的方法，依次将每一个点作为根结点，然后递归左右子树，可是在这个递归中有个问题，怎样推断递归结束，怎样保留上层的结点，怎样推断递归的是左子树还是有子树，递归的写法还是非常重要的。本题中，採用每次先求得下层子树左右子树的结点，然后依据左右子树的不同情况形成不同的树，保存这些树的根结点。
代码例如以下：
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
return constructTree(0,n-1);
}
vector<TreeNode*> constructTree(int startIndex, int endIndex){
vector<TreeNode *> result; //保存下一层的结点
if(startIndex > endIndex){
result.push_back(NULL);
return result;
}
for(int i=startIndex; i<=endIndex; ++i){
vector<TreeNode*> leftTrees = constructTree(startIndex,i-1);
vector<TreeNode*> rightTrees = constructTree(i+1,endIndex);
for(int j=0; j<leftTrees.size(); ++j){
for(int k=0; k<rightTrees.size(); ++k){
TreeNode * newNode = new TreeNode(i+1);
result.push_back(newNode);
newNode->left = leftTrees[j];
newNode->right = rightTrees[k];
}
}
}
return result;
}
};2、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
分析：先做上面的题，后面这个题就简单了，採用递归，每次计算下层的左子树和右子树的数目，本层的不同树的个数为左子树的数目与右子树的数目相乘，每种不同的情况相加就可以。
class Solution {
public:
int numTrees(int n) {
if(n < 1){
return 1;
}
return numTrees(1,n);
}
int numTrees(int startIndex, int endIndex){
int num = 1;
if(startIndex > endIndex){
return num;
}
num = 0;
for(int i=startIndex; i<=endIndex; ++i){
int leftNum = numTrees(startIndex,i-1);
int rightNum = numTrees(i+1,endIndex);
num += leftNum * rightNum;
}
return num;
}
};