r*********u
发帖数: 75 | 1 You have two BST, you have to merge them into a single BST, inplace and
linear time. |
g**e
发帖数: 6127 | 2 递归算in place吗
【在 r*********u 的大作中提到】
: You have two BST, you have to merge them into a single BST, inplace and
: linear time.
|
f*****w
发帖数: 2602 | |
h*********n
发帖数: 11319 | 4 will this work?
If the root of A < the root of B:
A1 = A.right
A.right = NULL
Merge A with B.left
Merge A1 with B.right
Otherwise:
A1 = A.left
A.left = NULL
Merge A1 with B.left
Merge A with B.right
【在 r*********u 的大作中提到】
: You have two BST, you have to merge them into a single BST, inplace and
: linear time.
|
g**e
发帖数: 6127 | 5 http://dzmitryhuba.blogspot.com/2011/03/merge-binary-search-tre
【在 r*********u 的大作中提到】
: You have two BST, you have to merge them into a single BST, inplace and
: linear time.
|
i**********e
发帖数: 1145 | 6 基本上是以下这两种解法合并起来 (Convert two BST to linked list in place,
merge two lists, then convert the list back to BST)。当然，中间有个 merge
linked list，很直接。
最难的部分是 convert list to BST，这解法用了 bottom-up DFS 的巧妙之处，利用链表的排序来建立 BST.
http://www.ihas1337code.com/2010/11/convert-binary-search-tree- （这个是 convert to doubly linked list，single linked list 要更简单些）
http://www.ihas1337code.com/2010/11/convert-sorted-list-to-bala
【在 r*********u 的大作中提到】
: You have two BST, you have to merge them into a single BST, inplace and
: linear time.
|
g**e
发帖数: 6127 | 7 学习
用链表的排序来建立 BST.
【在 i**********e 的大作中提到】
: 基本上是以下这两种解法合并起来 (Convert two BST to linked list in place,
: merge two lists, then convert the list back to BST)。当然，中间有个 merge
: linked list，很直接。
: 最难的部分是 convert list to BST，这解法用了 bottom-up DFS 的巧妙之处，利用链表的排序来建立 BST.
: http://www.ihas1337code.com/2010/11/convert-binary-search-tree- （这个是 convert to doubly linked list，single linked list 要更简单些）
: http://www.ihas1337code.com/2010/11/convert-sorted-list-to-bala
|
g**e
发帖数: 6127 | 8 convert bst to single linked list in-place感觉比convert成doubly linked list
还难一些。tree rotation感觉写起来挺麻烦的，不知道有没有简洁的方法？转doubly
linked list写递归很容易。
用链表的排序来建立 BST.
【在 i**********e 的大作中提到】
: 基本上是以下这两种解法合并起来 (Convert two BST to linked list in place,
: merge two lists, then convert the list back to BST)。当然，中间有个 merge
: linked list，很直接。
: 最难的部分是 convert list to BST，这解法用了 bottom-up DFS 的巧妙之处，利用链表的排序来建立 BST.
: http://www.ihas1337code.com/2010/11/convert-binary-search-tree- （这个是 convert to doubly linked list，single linked list 要更简单些）
: http://www.ihas1337code.com/2010/11/convert-sorted-list-to-bala
|
i**********e
发帖数: 1145 | 9 把 inorder traversal 稍微修改下就行了
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
list
doubly
【在 g**e 的大作中提到】
: convert bst to single linked list in-place感觉比convert成doubly linked list
: 还难一些。tree rotation感觉写起来挺麻烦的，不知道有没有简洁的方法？转doubly
: linked list写递归很容易。
:
: 用链表的排序来建立 BST.
|
s*****y
发帖数: 897 | 10 在网上找到一个merge的算法，很牛B，短短几行code就merge好了，verify过是work的
Tree *insert_node_in_tree(Tree *t1 , Tree *t2)
{
if(t1==NULL)
{
t2->left=NULL;
t2->right=NULL;
return t2;
}
if(t2->elementelement)
{
t1->left = insert_node_in_tree(t1->left , t2);
return t1;
}
else if(t2->element > t1->element)
{
t1->right = insert_node_in_tree(t1->right , t2);
return t1;
}
else
{
printf("Duplicate , here you can delete the node\n");
free(t2);
return NULL;
}
}
void merge_tree(Tree *t1, Tree *t2)
{
if(t2)
{
merge_tree(t1 , t2->left);
merge_tree(t1 , t2->right);
insert_node_in_tree(t1 , t2);
}
}
list
doubly
【在 g**e 的大作中提到】
: convert bst to single linked list in-place感觉比convert成doubly linked list
: 还难一些。tree rotation感觉写起来挺麻烦的，不知道有没有简洁的方法？转doubly
: linked list写递归很容易。
:
: 用链表的排序来建立 BST.
|
|
|
g**e
发帖数: 6127 | 11 赞，谢谢
【在 s*****y 的大作中提到】
: 在网上找到一个merge的算法，很牛B，短短几行code就merge好了，verify过是work的
: Tree *insert_node_in_tree(Tree *t1 , Tree *t2)
: {
: if(t1==NULL)
: {
: t2->left=NULL;
: t2->right=NULL;
: return t2;
: }
: if(t2->elementelement)
|
i**********e
发帖数: 1145 | 12 这个是可以，但是生成的树不一定 balanced，所以 worst case 有可能是 O(m * n)。
我之前给的算法 还有 gate 贴的联接的算法基本是一样的，可以保证 O(m+n) 还有结
合的树是 balanced 的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*****y 的大作中提到】
: 在网上找到一个merge的算法，很牛B，短短几行code就merge好了，verify过是work的
: Tree *insert_node_in_tree(Tree *t1 , Tree *t2)
: {
: if(t1==NULL)
: {
: t2->left=NULL;
: t2->right=NULL;
: return t2;
: }
: if(t2->elementelement)
|
s*****y
发帖数: 897 | 13 1. Does the question require balanced?
2. Does it require O(1) space. If so, this answer does not work as it push
all the elements onto the stack. |
i**********e
发帖数: 1145 | 14 1. No it does not require it to be balanced. But the algorithm you posted
basically is a variation of inserting nodes in a BST. Inserting a node in a
BST takes O(height of tree) time. If the tree is not balanced, the worst
case is O(mn) time. Even if the tree is balanced, it still takes O(m log n)
time (ie, not linear).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*****y 的大作中提到】
: 1. Does the question require balanced?
: 2. Does it require O(1) space. If so, this answer does not work as it push
: all the elements onto the stack.
|
s*****y
发帖数: 897 | 15 是啊,看来这个也不行.
a
)
【在 i**********e 的大作中提到】
: 1. No it does not require it to be balanced. But the algorithm you posted
: basically is a variation of inserting nodes in a BST. Inserting a node in a
: BST takes O(height of tree) time. If the tree is not balanced, the worst
: case is O(mn) time. Even if the tree is balanced, it still takes O(m log n)
: time (ie, not linear).
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
w**s
发帖数: 141 | 16 我觉得就是就是把一颗树in order traverse 一遍，每得到一个node 就 insert 到另
一个tree里就行了把。 Tree Tranverse time complex is O(n). and insert into
one of the trees is in place. Code as below:
Suppose we have two trees, Tree A and Tree B. Let's merge Tree B into Tree
A.
void main(){
// visit every node of B and insert it into A
InorderTranverse(B);
}
void InorderTranverse(Node *root){
if (root == null), return;
InorderTranverse(root->left);
// get root and insert into the other Tree
InsertIntoBST(A, root->value);
InorderTranverse(root->right);
}
void InsertIntoBST(Node *root, int key){
if ((root == null )|| (root.value == key)) return;
if ( key < root->value), InsertIntoBST(root->left, key);
if ( key > root->value), InsertIntoBST(root->right, key);
}
I think this works?? Any one see any problems? |
w**s
发帖数: 141 | 17 oh, that's right!
That's not liner!!
a
)
【在 i**********e 的大作中提到】
: 1. No it does not require it to be balanced. But the algorithm you posted
: basically is a variation of inserting nodes in a BST. Inserting a node in a
: BST takes O(height of tree) time. If the tree is not balanced, the worst
: case is O(mn) time. Even if the tree is balanced, it still takes O(m log n)
: time (ie, not linear).
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
m**q
发帖数: 189 | 18 刚才想到一个方法不知道能不能work...
同时对两个BST做in-order遍历，相当于同时遍历两个链表做merge，
把第一个BST的每一个元素插到第二个BST中的合适的位置。
注意这里的插入是一个修改过的插入，即并不从第二个BST的
root开始查找，而且也不限制只能在叶节点插入，而是比较
它和第二个BST当前元素的相对大小，决定是插入作为当前
元素的子节点，还是遍历第二个BST的下一个元素。应该
还是O(n)的。
最大的问题是这样做出来的BST会很不balanace，不如你上面
方法好。
a
)
【在 i**********e 的大作中提到】
: 1. No it does not require it to be balanced. But the algorithm you posted
: basically is a variation of inserting nodes in a BST. Inserting a node in a
: BST takes O(height of tree) time. If the tree is not balanced, the worst
: case is O(mn) time. Even if the tree is balanced, it still takes O(m log n)
: time (ie, not linear).
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
f*****w
发帖数: 2602 | 19
虽然我一时间没想到反例 但是这个真work么？ 有点怀疑
【在 s*****y 的大作中提到】
: 在网上找到一个merge的算法，很牛B，短短几行code就merge好了，verify过是work的
: Tree *insert_node_in_tree(Tree *t1 , Tree *t2)
: {
: if(t1==NULL)
: {
: t2->left=NULL;
: t2->right=NULL;
: return t2;
: }
: if(t2->elementelement)
|
W**********r
发帖数: 8927 | |
|
|
P**********c
发帖数: 3417 | 21 你这个解法从linked list到tree好像不是in place啊。
用链表的排序来建立 BST.
【在 i**********e 的大作中提到】
: 基本上是以下这两种解法合并起来 (Convert two BST to linked list in place,
: merge two lists, then convert the list back to BST)。当然，中间有个 merge
: linked list，很直接。
: 最难的部分是 convert list to BST，这解法用了 bottom-up DFS 的巧妙之处，利用链表的排序来建立 BST.
: http://www.ihas1337code.com/2010/11/convert-binary-search-tree- （这个是 convert to doubly linked list，single linked list 要更简单些）
: http://www.ihas1337code.com/2010/11/convert-sorted-list-to-bala
|
P**********c
发帖数: 3417 | 22 你这个解法从linked list到tree好像不是in place啊。
用链表的排序来建立 BST.
【在 i**********e 的大作中提到】
: 基本上是以下这两种解法合并起来 (Convert two BST to linked list in place,
: merge two lists, then convert the list back to BST)。当然，中间有个 merge
: linked list，很直接。
: 最难的部分是 convert list to BST，这解法用了 bottom-up DFS 的巧妙之处，利用链表的排序来建立 BST.
: http://www.ihas1337code.com/2010/11/convert-binary-search-tree- （这个是 convert to doubly linked list，single linked list 要更简单些）
: http://www.ihas1337code.com/2010/11/convert-sorted-list-to-bala
|
a********m
发帖数: 15480 | 23 这个是linear time么？
【在 s*****y 的大作中提到】
: 在网上找到一个merge的算法，很牛B，短短几行code就merge好了，verify过是work的
: Tree *insert_node_in_tree(Tree *t1 , Tree *t2)
: {
: if(t1==NULL)
: {
: t2->left=NULL;
: t2->right=NULL;
: return t2;
: }
: if(t2->elementelement)
|
a********m
发帖数: 15480 | 24 这个题算基本功了，不算bt吧。当然真正bt的题目也不少。
【在 W**********r 的大作中提到】
: 这种变态公司，不去也罢
|
w****r
发帖数: 245 | 25 要O(n)能想到的只有两树同时遍历，类似于mergesort那种
但是inplace确实很难唉
【在 r*********u 的大作中提到】
: You have two BST, you have to merge them into a single BST, inplace and
: linear time.
|
w****r
发帖数: 245 | 26 不过如果BST每个节点有指向parent的指针，倒是也可以O(1) space
【在 w****r 的大作中提到】
: 要O(n)能想到的只有两树同时遍历，类似于mergesort那种
: 但是inplace确实很难唉
|
m**q
发帖数: 189 | 27 用了递归，如果不算递归的stack的话是in-place的
【在 P**********c 的大作中提到】
: 你这个解法从linked list到tree好像不是in place啊。
:
: 用链表的排序来建立 BST.
|
