K******g
发帖数: 1870 | 1 请问排过序的list组建一个bst，怎么做呢，复杂度是多少？谢谢 |
b********h
发帖数: 119 | 2 bst的inorder traversal就是一个有序的list，但从一个有序list还原到bst不是唯一
的。最简单的可以遍历这个list，把每个元素加到bst的左边（原list按降序排列）或
右边（原list按升序排列）。但这样出来的bst的高度就是list的长度，所以是最差的
bst。好点的做法可以每次取list中间的元素作为root，然后递归的建左子树和右子树
。这两个的复杂度都是O（n）。 |
D****6
发帖数: 278 | 3 第二个做法为什么不是nlogn??
【在 b********h 的大作中提到】
: bst的inorder traversal就是一个有序的list，但从一个有序list还原到bst不是唯一
: 的。最简单的可以遍历这个list，把每个元素加到bst的左边（原list按降序排列）或
: 右边（原list按升序排列）。但这样出来的bst的高度就是list的长度，所以是最差的
: bst。好点的做法可以每次取list中间的元素作为root，然后递归的建左子树和右子树
: 。这两个的复杂度都是O（n）。
|
i*****r
发帖数: 265 | 4 要是每次取中点的那种就是nlogn啦，说n的都是默认取中点是O(1)的……对于链表明
显不对。dsw好像可以是n的，但是要面试的时候搞出来不容易吧 |
r****c
发帖数: 2585 | 5 haha
你应该告诉面试的人
一直放rchild, haha
degenerated bst
【在 K******g 的大作中提到】
: 请问排过序的list组建一个bst，怎么做呢，复杂度是多少？谢谢
|
h**k
发帖数: 3368 | 6 可以用递归来实现。对链表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的，但是要面试的时候搞出来不容易吧
|
