y*n
2 楼
盖里奇间谍新片放出Comin-Con预告
妙趣横生
妙趣横生
i*t
3 楼
说的是 “我也要任性一回”。。。。。。。
b*h
4 楼
bst的inorder traversal就是一个有序的list，但从一个有序list还原到bst不是唯一
的。最简单的可以遍历这个list，把每个元素加到bst的左边（原list按降序排列）或
右边（原list按升序排列）。但这样出来的bst的高度就是list的长度，所以是最差的
bst。好点的做法可以每次取list中间的元素作为root，然后递归的建左子树和右子树
。这两个的复杂度都是O（n）。
的。最简单的可以遍历这个list，把每个元素加到bst的左边（原list按降序排列）或
右边（原list按升序排列）。但这样出来的bst的高度就是list的长度，所以是最差的
bst。好点的做法可以每次取list中间的元素作为root，然后递归的建左子树和右子树
。这两个的复杂度都是O（n）。
g*n
5 楼
看起来不错
D*6
6 楼
第二个做法为什么不是nlogn??
【在 b********h 的大作中提到】
: bst的inorder traversal就是一个有序的list，但从一个有序list还原到bst不是唯一
: 的。最简单的可以遍历这个list，把每个元素加到bst的左边（原list按降序排列）或
: 右边（原list按升序排列）。但这样出来的bst的高度就是list的长度，所以是最差的
: bst。好点的做法可以每次取list中间的元素作为root，然后递归的建左子树和右子树
: 。这两个的复杂度都是O（n）。
【在 b********h 的大作中提到】
: bst的inorder traversal就是一个有序的list，但从一个有序list还原到bst不是唯一
: 的。最简单的可以遍历这个list，把每个元素加到bst的左边（原list按降序排列）或
: 右边（原list按升序排列）。但这样出来的bst的高度就是list的长度，所以是最差的
: bst。好点的做法可以每次取list中间的元素作为root，然后递归的建左子树和右子树
: 。这两个的复杂度都是O（n）。
i*r
7 楼
要是每次取中点的那种就是nlogn啦，说n的都是默认取中点是O(1)的……对于链表明
显不对。dsw好像可以是n的，但是要面试的时候搞出来不容易吧
显不对。dsw好像可以是n的，但是要面试的时候搞出来不容易吧
r*c
8 楼
haha
你应该告诉面试的人
一直放rchild, haha
degenerated bst
【在 K******g 的大作中提到】
: 请问排过序的list组建一个bst，怎么做呢，复杂度是多少？谢谢
你应该告诉面试的人
一直放rchild, haha
degenerated bst
【在 K******g 的大作中提到】
: 请问排过序的list组建一个bst，怎么做呢，复杂度是多少？谢谢
h*k
9 楼
可以用递归来实现。对链表O(n)
初始call
build_bst( list_head, list_length);
Node* build_bst( Node* &list_cur, int n )
{
if( n == 0 )
return null;
Node * p = build_bst( list_cur, n/2);
list_cur->left = p;
p = list_cur;
list_cur = list_cur->next;
p->right = build_bst( list_cur, n-1-n/2);
return p;
}
【在 i*****r 的大作中提到】
: 要是每次取中点的那种就是nlogn啦，说n的都是默认取中点是O(1)的……对于链表明
: 显不对。dsw好像可以是n的，但是要面试的时候搞出来不容易吧
初始call
build_bst( list_head, list_length);
Node* build_bst( Node* &list_cur, int n )
{
if( n == 0 )
return null;
Node * p = build_bst( list_cur, n/2);
list_cur->left = p;
p = list_cur;
list_cur = list_cur->next;
p->right = build_bst( list_cur, n-1-n/2);
return p;
}
【在 i*****r 的大作中提到】
: 要是每次取中点的那种就是nlogn啦，说n的都是默认取中点是O(1)的……对于链表明
: 显不对。dsw好像可以是n的，但是要面试的时候搞出来不容易吧
相关阅读