l*********y
发帖数: 142 | 1 given two binary search trees, merge them in O(n) time with O(1) space.
(Converting them to link lists does not work since it require O(n) extra
pointer space)
谁能给讲一讲。
谢谢！ |
a**********s
发帖数: 588 | 2 我觉得基本思路可以是这样子的:
Non-recursively访问第二个BST的每一个节点（这样的话，得到的是从小到大的顺序，
并且时间空间复杂度分别是O(N2)和O(1)），一个一个的插入到第一个BSP，假设每一步
待插入的node为BN2。然后第一个BSP也是non-recursively访问，并保持前后相继的两
个结点指针L1和L2，使得
L1->data <= BN2->data <= L2->data
注意到要么L1的右儿子为空，要么L2的左儿子为空，这样插入每一个节点的复杂度应该也是O(1)，所以总的时间为O(n)
【在 l*********y 的大作中提到】
: given two binary search trees, merge them in O(n) time with O(1) space.
: (Converting them to link lists does not work since it require O(n) extra
: pointer space)
: 谁能给讲一讲。
: 谢谢！
|
r****o
发帖数: 1950 | 3 为什么要么L1的右儿子为空，要么L2的左儿子为空呢？
该也是O(1)，所以总的时间为O(n)
【在 a**********s 的大作中提到】
: 我觉得基本思路可以是这样子的:
: Non-recursively访问第二个BST的每一个节点（这样的话，得到的是从小到大的顺序，
: 并且时间空间复杂度分别是O(N2)和O(1)），一个一个的插入到第一个BSP，假设每一步
: 待插入的node为BN2。然后第一个BSP也是non-recursively访问，并保持前后相继的两
: 个结点指针L1和L2，使得
: L1->data <= BN2->data <= L2->data
: 注意到要么L1的右儿子为空，要么L2的左儿子为空，这样插入每一个节点的复杂度应该也是O(1)，所以总的时间为O(n)
|
f*******e
发帖数: 1161 | 4 不是相当于遍历两颗树么？
比如分别先根遍历，每访问一个接点，把该节点断开，这样可行么？
【在 l*********y 的大作中提到】
: given two binary search trees, merge them in O(n) time with O(1) space.
: (Converting them to link lists does not work since it require O(n) extra
: pointer space)
: 谁能给讲一讲。
: 谢谢！
|
a**********s
发帖数: 588 | 5 因为L1和L2是前后相继的两个结点，其中有一个必然为另外一个的祖先，否则的话，他
们的共同祖先在他们中间。
然后，如果L1为L2的祖先，那么L2在L1的右子树，那么L2的左儿子必然为空，否则的话
，L2的左儿子在L1和L2中间。
同理可证L2为L1的祖先的情况下，L1的右儿子为空。
我明白了你为什么困惑了，我前面忘了写L1和L2前后相继了，现在改过来了。
【在 r****o 的大作中提到】
: 为什么要么L1的右儿子为空，要么L2的左儿子为空呢？
:
: 该也是O(1)，所以总的时间为O(n)
|
k**********i
发帖数: 177 | 6 你怎么读第二个bst的每一个节点是从小到大？inorder？，并且读的复杂度不是O（n）
？ 为啥？
该也是
O(1)，所以总的时间为O(n)
【在 a**********s 的大作中提到】
: 我觉得基本思路可以是这样子的:
: Non-recursively访问第二个BST的每一个节点（这样的话，得到的是从小到大的顺序，
: 并且时间空间复杂度分别是O(N2)和O(1)），一个一个的插入到第一个BSP，假设每一步
: 待插入的node为BN2。然后第一个BSP也是non-recursively访问，并保持前后相继的两
: 个结点指针L1和L2，使得
: L1->data <= BN2->data <= L2->data
: 注意到要么L1的右儿子为空，要么L2的左儿子为空，这样插入每一个节点的复杂度应该也是O(1)，所以总的时间为O(n)
|
l*********y
发帖数: 142 | 7 想了一下，感觉你说的是对的。而且这个题non-recursive的implementation似乎要比
recursive简单一些。
【在 a**********s 的大作中提到】
: 因为L1和L2是前后相继的两个结点，其中有一个必然为另外一个的祖先，否则的话，他
: 们的共同祖先在他们中间。
: 然后，如果L1为L2的祖先，那么L2在L1的右子树，那么L2的左儿子必然为空，否则的话
: ，L2的左儿子在L1和L2中间。
: 同理可证L2为L1的祖先的情况下，L1的右儿子为空。
: 我明白了你为什么困惑了，我前面忘了写L1和L2前后相继了，现在改过来了。
|
r****o
发帖数: 1950 | 8 你是说两个都以non-recursive的inorder访问?
我有个疑问是，对于第二个BST的每一个节点，怎么找到第一个BST的一对L1和L2呢？
这里是不是要用到binary search?
该也是O(1)，所以总的时间为O(n)
【在 a**********s 的大作中提到】
: 我觉得基本思路可以是这样子的:
: Non-recursively访问第二个BST的每一个节点（这样的话，得到的是从小到大的顺序，
: 并且时间空间复杂度分别是O(N2)和O(1)），一个一个的插入到第一个BSP，假设每一步
: 待插入的node为BN2。然后第一个BSP也是non-recursively访问，并保持前后相继的两
: 个结点指针L1和L2，使得
: L1->data <= BN2->data <= L2->data
: 注意到要么L1的右儿子为空，要么L2的左儿子为空，这样插入每一个节点的复杂度应该也是O(1)，所以总的时间为O(n)
|
x***y
发帖数: 633 | 9 How can you inorder traverse the 2nd BST in O(1) space? At least a stack is
needed for non-recursive method.....In essence, what trick in your method
makes the space from O(n), in flattening and merging method, to O(1). thanks a lot
...
该也是O(1)，所以总的时间为O(n)
【在 a**********s 的大作中提到】
: 我觉得基本思路可以是这样子的:
: Non-recursively访问第二个BST的每一个节点（这样的话，得到的是从小到大的顺序，
: 并且时间空间复杂度分别是O(N2)和O(1)），一个一个的插入到第一个BSP，假设每一步
: 待插入的node为BN2。然后第一个BSP也是non-recursively访问，并保持前后相继的两
: 个结点指针L1和L2，使得
: L1->data <= BN2->data <= L2->data
: 注意到要么L1的右儿子为空，要么L2的左儿子为空，这样插入每一个节点的复杂度应该也是O(1)，所以总的时间为O(n)
|
a**********s
发帖数: 588 | 10 明白大家为什么困惑了，non-resursive BST traversal是基本的二叉树操作，只需要线性时间和常数空间复杂度，但是需要一个父指针。。。
没有父指针的二叉树合并，好像也是可以做的，我再想想。 |
|
|
k***e
发帖数: 556 | 11 please check DSW algorithm
【在 l*********y 的大作中提到】
: given two binary search trees, merge them in O(n) time with O(1) space.
: (Converting them to link lists does not work since it require O(n) extra
: pointer space)
: 谁能给讲一讲。
: 谢谢！
|
g*****u
发帖数: 298 | 12 呵呵，我以前也问过这个题目。就是DSW，先把两个BST通过旋转变为两个link list，
再merge，再旋转为满二叉树。
【在 k***e 的大作中提到】
: please check DSW algorithm
|
l*********y
发帖数: 142 | 13 请问这个不是space O(n) 吗？
【在 g*****u 的大作中提到】
: 呵呵，我以前也问过这个题目。就是DSW，先把两个BST通过旋转变为两个link list，
: 再merge，再旋转为满二叉树。
|
p******o
发帖数: 125 | 14 Inplace的啊
【在 l*********y 的大作中提到】
: 请问这个不是space O(n) 吗？
|
c***p
发帖数: 221 | 15 if re-use the left and right pointer in nodes of binary search tree as prev
and next pointer to build a linked-list, no extra O(n) space is needed.
【在 l*********y 的大作中提到】
: given two binary search trees, merge them in O(n) time with O(1) space.
: (Converting them to link lists does not work since it require O(n) extra
: pointer space)
: 谁能给讲一讲。
: 谢谢！
|
s******9
发帖数: 84 | 16 没有父指针的话，需要有一个龙lg(n)的stack。在O(1)额外内存的限制下，只能是把两
棵树都用连续的左转操作转换成List，合并后再右转操作成一颗平衡二叉树。
要线性时间和常数空间复杂度，但是需要一个父指针。。。
【在 a**********s 的大作中提到】
: 明白大家为什么困惑了，non-resursive BST traversal是基本的二叉树操作，只需要线性时间和常数空间复杂度，但是需要一个父指针。。。
: 没有父指针的二叉树合并，好像也是可以做的，我再想想。
|
