LeetCode: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
分析：依次把每个节点作为根节点，左边节点作为左子树，右边节点作为右子树，那么总的数目等于左子树数目*右子树数目，实际只要求出前半部分节点作为根节点的树的数目，然后乘以2（奇数个节点还要加上中间节点作为根的二叉树数目）
递归代码：为了避免重复计算子问题，用数组保存已经计算好的结果
class Solution {
public:
int numTrees(int n) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int nums[n+]; //nums[i]表示i个节点的二叉查找树的数目
memset(nums, , sizeof(nums));
return numTreesRecur(n, nums);
}
int numTreesRecur(int n, int nums[])
{
if(nums[n] != )return nums[n];
if(n == ){nums[] = ; return ;}
int tmp = (n>>);
for(int i = ; i <= tmp; i++)
{
int left,right;
if(nums[i-])left = nums[i-];
else left = numTreesRecur(i-, nums);
if(nums[n-i])right = nums[n-i];
else right = numTreesRecur(n-i, nums);
nums[n] += left*right;
}
nums[n] <<= ;
if(n % != )
{
int val;
if(nums[tmp])val = nums[tmp];
else val = numTreesRecur(tmp, nums);
nums[n] += val*val;
}
return nums[n];
}
};
非递归代码：从0个节点的二叉查找树数目开始自底向上计算，dp方程为nums[i] = sum(nums[k-1]*nums[i-k]) (k = 1,2,3...i)
class Solution {
public:
int numTrees(int n) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int nums[n+]; //num[i]表示i个节点的二叉查找树数目
memset(nums, , sizeof(nums));
nums[] = ;
for(int i = ; i <= n; i++)
{
int tmp = (i>>);
for(int j = ; j <= tmp; j++)
nums[i] += nums[j-]*nums[i-j];
nums[i] <<= ;
if(i % != )
nums[i] += nums[tmp]*nums[tmp];
}
return nums[n];
}
};
LeetCode: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
按照上一题的思路，我们不仅仅要保存i个节点对应的BST树的数目，还要保存所有的BST树，而且1、2、3和4、5、6虽然对应的BST数目和结构一样，但是BST树是不一样的，因为节点值不同。
我们用数组btrees[i][j][]保存节点i, i+1,...j-1,j构成的所有二叉树，从节点数目为1的的二叉树开始自底向上最后求得节点数目为n的所有二叉树 本文地址
/**
* 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 *> generateTrees(int n) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
vector<vector<vector<TreeNode*> > > btrees(n+, vector<vector<TreeNode*> >(n+, vector<TreeNode*>()));
for(int i = ; i <= n+; i++)
btrees[i][i-].push_back(NULL); //为了下面处理btrees[i][j]时 i > j的边界情况
for(int k = ; k <= n; k++)//k表示节点数目
for(int i = ; i <= n-k+; i++)//i表示起始节点
{
for(int rootval = i; rootval <= k+i-; rootval++)
{//求[i,i+1,...i+k-1]序列对应的所有BST树
for(int m = ; m < btrees[i][rootval-].size(); m++)//左子树
for(int n = ; n < btrees[rootval+][k+i-].size(); n++)//右子树
{
TreeNode *root = new TreeNode(rootval);
root->left = btrees[i][rootval-][m];
root->right = btrees[rootval+][k+i-][n];
btrees[i][k+i-].push_back(root);
}
}
}
return btrees[][n];
}
};
【版权声明】转载请注明出处：http://www.cnblogs.com/TenosDoIt/p/3448569.html