g*****u
发帖数: 298 | 1 合并两个BST要求O(n+m)时间，n和m为两棵树的大小。有什么好的解法么？ |
g*******y
发帖数: 1930 | 2 DSW
特别提醒mm们：不是指卖靴子的！
【在 g*****u 的大作中提到】
: 合并两个BST要求O(n+m)时间，n和m为两棵树的大小。有什么好的解法么？
|
r****o
发帖数: 1950 | 3 what does DSW mean?
【在 g*******y 的大作中提到】
: DSW
: 特别提醒mm们：不是指卖靴子的！
|
g*******y
发帖数: 1930 | 4 http://www.dsw.com/dsw_shoes/catalog/index.jsp
Women's Shoes Online at DSW: Boots, Fall Shoes, Winter Shoes ...
呵呵，just kidding～
【在 r****o 的大作中提到】
: what does DSW mean?
|
m*******y
发帖数: 68 | |
m*******y
发帖数: 68 | 6 呼唤厚道
【在 g*******y 的大作中提到】
: http://www.dsw.com/dsw_shoes/catalog/index.jsp
: Women's Shoes Online at DSW: Boots, Fall Shoes, Winter Shoes ...
: 呵呵，just kidding～
|
g*****u
发帖数: 298 | 7 呵呵谢谢大家
这是不是就是说，先把两个BST转成linked list,再merge sort，再rotate成balanced
BST呢。
【在 m*******y 的大作中提到】
: 呼唤厚道
|
H*M
发帖数: 1268 | 8 不是mergesort是merge.因为两边sort好了
所以才能O(n+m)吧
balanced
【在 g*****u 的大作中提到】
: 呵呵谢谢大家
: 这是不是就是说，先把两个BST转成linked list,再merge sort，再rotate成balanced
: BST呢。
|
r*****t
发帖数: 712 | 9 in-order traverse both bst, merger the result, construct a new bst
【在 g*****u 的大作中提到】
: 合并两个BST要求O(n+m)时间，n和m为两棵树的大小。有什么好的解法么？
|
c****p
发帖数: 32 | 10 what's the point?
只是要O(n+m)的时间，又没限定空间，直接copy，然后建一个bst不就完了？
balanced
【在 g*****u 的大作中提到】
: 呵呵谢谢大家
: 这是不是就是说，先把两个BST转成linked list,再merge sort，再rotate成balanced
: BST呢。
|
|
|
g*******y
发帖数: 1930 | 11 得自己给自己增加些难度嘛。。。要求in place
你面试的时候先说一个非 in place的，估计面试官多半会继续让你想一个in place的
我虽然面试的不多，但是感觉的出来，面试官们都很喜欢问了一个问题后，不停的问更好的方法，不同的方法，或者修改条件，加限制，变一下题目，换着法子的问。所以我们做题绝对不能够仅仅限于做个题有一个方法就满足了，要不停的多想想你是面试官会怎么换着法子变化。
【在 c****p 的大作中提到】
: what's the point?
: 只是要O(n+m)的时间，又没限定空间，直接copy，然后建一个bst不就完了？
:
: balanced
|
s*******a
发帖数: 42 | 12 in place 的话对树递归遍历时需要记录当前节点中的最大最小值就可以了 |
g*****u
发帖数: 298 | 13 我就是merge的意思。
我想知道，如果没看过DSW的话，你们能在面试时想出来这个办法么？
【在 H*M 的大作中提到】
: 不是mergesort是merge.因为两边sort好了
: 所以才能O(n+m)吧
:
: balanced
|
H*M
发帖数: 1268 | 14 no
【在 g*****u 的大作中提到】
: 我就是merge的意思。
: 我想知道，如果没看过DSW的话，你们能在面试时想出来这个办法么？
|
m*****f
发帖数: 1243 | 15 我想不出来..
【在 g*****u 的大作中提到】
: 我就是merge的意思。
: 我想知道，如果没看过DSW的话，你们能在面试时想出来这个办法么？
|
p********7
发帖数: 549 | 16 in-order traverse both bst, merger the result, construct a new bst不是么？
【在 m*****f 的大作中提到】
: 我想不出来..
|
r****o
发帖数: 1950 | 17 光凭in-order traversal result怎么construct a new bst?
【在 p********7 的大作中提到】
: in-order traverse both bst, merger the result, construct a new bst不是么？
|
y*c
发帖数: 904 | 18 首先没说是balanced, 直接用递归插就行了。
如果要balanced, 就算知道DSW, 你能写出来code么？能保证对么？我被面过这道题，
用的是多于空间,traverse, merge and construct方法，是可以写出来的。窃以为面试
就足够了，当然，你可以说，如果不要多余space,就用rotation -> right deep
然后 折半rotation变成balanced bst. |
p********7
发帖数: 549 | 19 同时遍历2个树，如果一个树比如是A节点小于另外一个树B的节点，那么就把这个小的
加在另外一个树节点的左边。然后再接着遍历A的下个节点，这个节点比上个节点大。
如果这个节点仍小于B的第一个，那么就把它加入B的左节点；如果比B第一个大，那么
就继续遍历B的第二个节点，看是不是比第二个大，直到在B的2个节点大小之间的时候
，然后插入。
【在 r****o 的大作中提到】
: 光凭in-order traversal result怎么construct a new bst?
|
K******g
发帖数: 1870 | 20 construct a new BST, 不是要求nlogn 么？那就根本不对了，人家要求O(m+n)
【在 y*c 的大作中提到】
: 首先没说是balanced, 直接用递归插就行了。
: 如果要balanced, 就算知道DSW, 你能写出来code么？能保证对么？我被面过这道题，
: 用的是多于空间,traverse, merge and construct方法，是可以写出来的。窃以为面试
: 就足够了，当然，你可以说，如果不要多余space,就用rotation -> right deep
: 然后 折半rotation变成balanced bst.
|
|
|
h**k
发帖数: 3368 | 21 那是输入序列没有排序时的复杂度。
排过序的不用。
【在 K******g 的大作中提到】
: construct a new BST, 不是要求nlogn 么？那就根本不对了，人家要求O(m+n)
|
K******g
发帖数: 1870 | 22 请问排过序的list组建一个bst，怎么做呢，复杂度是多少？谢谢
【在 h**k 的大作中提到】
: 那是输入序列没有排序时的复杂度。
: 排过序的不用。
|
i*****r
发帖数: 265 | 23 要是要求balanced的话我只会nlogn的，不知道n的复杂度怎么搞。
【在 K******g 的大作中提到】
: 请问排过序的list组建一个bst，怎么做呢，复杂度是多少？谢谢
|
D****6
发帖数: 278 | 24 1. inorder traverse tree A and B, save sorted values in two arrays. (m+n)
2. merge two arrays into a bigger sorted array. (m+n)
3. use recursive binary search algorithm on the big sorted array, to
construct the new BST. (log(m+n))
so, total running time (m+n)
对吗? |
p**********s
发帖数: 115 | 25 最后一步应该是m+n.
【在 D****6 的大作中提到】
: 1. inorder traverse tree A and B, save sorted values in two arrays. (m+n)
: 2. merge two arrays into a bigger sorted array. (m+n)
: 3. use recursive binary search algorithm on the big sorted array, to
: construct the new BST. (log(m+n))
: so, total running time (m+n)
: 对吗?
|
h**k
发帖数: 3368 | 26 递归，需要知道list长度。
【在 i*****r 的大作中提到】
: 要是要求balanced的话我只会nlogn的，不知道n的复杂度怎么搞。
|
w*****1
发帖数: 245 | 27 recursion是log(m+n)depth, 每个level是(1).
不是这样分析阿?
【在 p**********s 的大作中提到】
: 最后一步应该是m+n.
|
m*****g
发帖数: 226 | 28 3.binary search on linked list is not lg
【在 D****6 的大作中提到】
: 1. inorder traverse tree A and B, save sorted values in two arrays. (m+n)
: 2. merge two arrays into a bigger sorted array. (m+n)
: 3. use recursive binary search algorithm on the big sorted array, to
: construct the new BST. (log(m+n))
: so, total running time (m+n)
: 对吗?
|
K******g
发帖数: 1870 | 29 请问use recursive binary search algorithm on the big sorted array, to |
p********7
发帖数: 549 | 30 他的意思不是让你重新建立，而是你在把一个树的node插入另外一个的时候，需要分配
1个node
【在 K******g 的大作中提到】
: construct a new BST, 不是要求nlogn 么？那就根本不对了，人家要求O(m+n)
|
