i**********e
发帖数: 1145 | 1 这道题大家做做看:
给定 n，生成所有不重复的 BSTs，里面节点所包含的值必须个别为 1 到 n。
input 是 n，output 是 list of |
f*****e
发帖数: 2992 | 2 递归看行不行。
【在 i**********e 的大作中提到】
: 这道题大家做做看:
: 给定 n，生成所有不重复的 BSTs，里面节点所包含的值必须个别为 1 到 n。
: input 是 n，output 是 list of
|
w****x
发帖数: 2483 | 3
这题就是for里递归吧
【在 i**********e 的大作中提到】
: 这道题大家做做看:
: 给定 n，生成所有不重复的 BSTs，里面节点所包含的值必须个别为 1 到 n。
: input 是 n，output 是 list of
|
l*****a
发帖数: 14598 | 4 牛
【在 w****x 的大作中提到】
:
: 这题就是for里递归吧
|
v***d
发帖数: 51 | 5 试着做了一下
Node* findAllBSTs(int beginIndex, int endIndex, Node* origHead, Node*
curParent) {
if ( endIndex - beginIndex < 0 )
return NULL;
else if ( endIndex - beginIndex == 0 ) {
Node* newNode = new Node(values[beginIndex], NULL, NULL);
return newNode;
}
else {
for ( int i = beginIndex; i <= endIndex; i++ ) {
curParent->value = values[i];
if ( beginIndex <= i-1 )
curParent->leftChild = new Node(0, NULL, NULL);
else
curParent->leftChild = NULL;
if ( i+1 <= endIndex )
curParent->rightChild = new Node(0, NULL, NULL);
else
curParent->rightChild = NULL;
curParent->leftChild = findAllBSTs(beginIndex, i-1, origHead,
curParent->leftChild);
curParent->rightChild = findAllBSTs(i+1, endIndex, origHead,
curParent->rightChild);
if ( beginIndex == i-1 && i+1 == endIndex ) {
//deep copy "orighead" to a global vector object
}
}
}
return NULL;
} |
i***e
发帖数: 452 | 6 感觉真心不好写啊这题！！！ 写了个有Bug的程序（晕死）：
struct node{
int value;
node* lchild;
node* rchild;
node(int v):value(v), lchild(0), rchild(0){};
};
vector help(int start, int end)
{
vector result;
if(start > end) return result;
if(start == end)
{
result.push_back(new node(start));
return result;
}
for(int i = start; i <= end; i++)
{
vector left = help(start, i-1);
vector right = help(i+1, end);
node* r = new node(i);
if(left.empty())
{
for(int j = 0; j < right.size(); j++)
{
r->rchild = right[j];
result.push_back(r);
}
}
else if(right.empty())
{
for(int j = 0; j < left.size(); j++)
{
r->lchild = left[j];
result.push_back(r);
}
}
else
{
for(int j = 0; j < left.size(); j++)
{
r->lchild = left[j];
for(int k = 0; k < right.size(); k++)
{
r->rchild = right[k];
result.push_back(r);
}
}
}
}
return result;
}
vector buildBSTs(int n)
{
return help(1,n);
} |
i***e
发帖数: 452 | 7 感觉思路是对的， 但是结果却有问题， 这个题目没有想象中那么简单..求大牛指点！
！ |
i***e
发帖数: 452 | 8 感觉不对啊！！ 你的应该比实际的解少的多？
【在 v***d 的大作中提到】
: 试着做了一下
: Node* findAllBSTs(int beginIndex, int endIndex, Node* origHead, Node*
: curParent) {
: if ( endIndex - beginIndex < 0 )
: return NULL;
: else if ( endIndex - beginIndex == 0 ) {
: Node* newNode = new Node(values[beginIndex], NULL, NULL);
: return newNode;
: }
: else {
|
s*****n
发帖数: 162 | 9 抛个砖。
n个节点的树和n对valid parentheses是一一对应的。可以每生成一个valid
parentheses string，然后生成一棵BST。 |
h*****n
发帖数: 188 | 10 2^n-n in total,
take 1~n as inorder traversal,
recursion i as root node, T(i) = T(i-1) + T(n-i) ?
【在 i**********e 的大作中提到】
: 这道题大家做做看:
: 给定 n，生成所有不重复的 BSTs，里面节点所包含的值必须个别为 1 到 n。
: input 是 n，output 是 list of
|
|
|
t*****l
发帖数: 241 | 11 that's my first thought, too. simple recursion can do the job.
【在 h*****n 的大作中提到】
: 2^n-n in total,
: take 1~n as inorder traversal,
: recursion i as root node, T(i) = T(i-1) + T(n-i) ?
|
i***e
发帖数: 452 | 12 right. Catalan numbers!!
【在 s*****n 的大作中提到】
: 抛个砖。
: n个节点的树和n对valid parentheses是一一对应的。可以每生成一个valid
: parentheses string，然后生成一棵BST。
|
i***e
发帖数: 452 | 13 that's wrong! please google "catalan numbers"
【在 h*****n 的大作中提到】
: 2^n-n in total,
: take 1~n as inorder traversal,
: recursion i as root node, T(i) = T(i-1) + T(n-i) ?
|
h****e
发帖数: 928 | 14 是的，又想起了趣味数学。
【在 i***e 的大作中提到】
: right. Catalan numbers!!
|
h*****n
发帖数: 188 | 15 I had a typo, the recursion should be multiplications
T(n) = \sum_i=0^(n-1) T(i)*T(n-1-i)
catalan numbers is correct, the recursions shows how "catalan numbers" are
calculated.
【在 i***e 的大作中提到】
: that's wrong! please google "catalan numbers"
|
l********7
发帖数: 19 | 16
记录结果实在是不容易。我能想到的方法，
得到所有可能的前序遍历，那么生成树就可以根据前序遍历序列(以及中序遍历)
一棵棵建立了。递归是很难得到所有的前序遍历了，那就迭代吧。
节点 k 作为 根节点， 1...k-1为左子树 (可能为空)， k + 1 ... n为右子树(可能为
空)
h(n) = h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)*h(0)
恩，应该就是卡塔兰数了。
构建树：
依次建立和记录
h(0) -- 空树
h(1) -- 一个点的树
h(2) -- 二个点的树
。。。
h(n-1)
序列h(n) 就可以通过 h(0) h(1)...h(n-1) 来建立了
这里要小心的是， 比如 考虑 h(k) * h(n - 1 - k)
连接序列 h(k) 这个集合和 h(n - 1 - k)时, 序列h(n - 1 - k)中的值都要加上一个
笃定的值, i.e., k + 1
这里的序列链接(* 运算)相当于笛卡尔积。
有错请指出！
【在 i**********e 的大作中提到】
: 这道题大家做做看:
: 给定 n，生成所有不重复的 BSTs，里面节点所包含的值必须个别为 1 到 n。
: input 是 n，output 是 list of
|
j*****o
发帖数: 394 | 17 求TEST...
list unique(int start, int end){
list res;
if(start > end) return res;
list leftChild,rightChild;
list::iterator iter1,iter2;
for(int i=start; i<=end; i++){
leftChild=unique(start,i-1);
rightChild=unique(i+1,end);
if(leftChild.empty()) leftChild.push_back(NULL);
if(rightChild.empty()) rightChild.push_back(NULL);
for(iter1=leftChild.begin(); iter1!=leftChild.end(); iter1++)
for(iter2=rightChild.begin(); iter2!=rightChild.end(); iter2++){
Node *root=new Node(i);
root->left=*iter1;
root->right=*iter2;
res.push_back(root);
}
}
return res;
}
list uniqueBST(int n){
return unique(1,n);
}
【在 i**********e 的大作中提到】
: 这道题大家做做看:
: 给定 n，生成所有不重复的 BSTs，里面节点所包含的值必须个别为 1 到 n。
: input 是 n，output 是 list of
|
c*****e
发帖数: 3226 | 18 http://cslibrary.stanford.edu/110/BinaryTrees.html#s2
question 12.
【在 i**********e 的大作中提到】
: 这道题大家做做看:
: 给定 n，生成所有不重复的 BSTs，里面节点所包含的值必须个别为 1 到 n。
: input 是 n，output 是 list of
|
i**********e
发帖数: 1145 | 19 已经收录了这题在 OJ "Unique Binary Search Trees II"，大家有兴趣可以测一下代
码. |
i***e
发帖数: 452 | 20 顶大牛的做的网站， 非常棒啊！！ 只是发现已经很久没有加新题目了。。
【在 i**********e 的大作中提到】
: 已经收录了这题在 OJ "Unique Binary Search Trees II"，大家有兴趣可以测一下代
: 码.
|
|
|
i**********e
发帖数: 1145 | 21 要加很多二叉树的题目了，敬请期待！
【在 i***e 的大作中提到】
: 顶大牛的做的网站， 非常棒啊！！ 只是发现已经很久没有加新题目了。。
|
w****x
发帖数: 2483 | 22
别加了, 够啦, 再加做不完又有负罪感了
【在 i**********e 的大作中提到】
: 要加很多二叉树的题目了，敬请期待！
|
i**********e
发帖数: 1145 | 23 不错！就是这样的简洁代码 :)
其实你可以删除以下这两行：
if(leftChild.empty()) leftChild.push_back(NULL);
if(rightChild.empty()) rightChild.push_back(NULL);
然后小心 handle start > end 的特殊状况 (n == 0 空树的情况? )：
if(start > end) {
res.push_back(NULL);
return res;
}
【在 j*****o 的大作中提到】
: 求TEST...
: list unique(int start, int end){
: list res;
: if(start > end) return res;
: list leftChild,rightChild;
: list::iterator iter1,iter2;
: for(int i=start; i<=end; i++){
: leftChild=unique(start,i-1);
: rightChild=unique(i+1,end);
: if(leftChild.empty()) leftChild.push_back(NULL);
|
h****e
发帖数: 928 | 24 不加的话你能做满800题吗？
【在 w****x 的大作中提到】
:
: 别加了, 够啦, 再加做不完又有负罪感了
|
e***s
发帖数: 799 | 25 泪牛满面，这要在interview问我，我就只能去死了
【在 j*****o 的大作中提到】
: 求TEST...
: list unique(int start, int end){
: list res;
: if(start > end) return res;
: list leftChild,rightChild;
: list::iterator iter1,iter2;
: for(int i=start; i<=end; i++){
: leftChild=unique(start,i-1);
: rightChild=unique(i+1,end);
: if(leftChild.empty()) leftChild.push_back(NULL);
|
