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 楼
看起来不错
i*r
7 楼
要是每次取中点的那种就是nlogn啦,说n的都是默认取中点是O(1)的……对于链表明
显不对。dsw好像可以是n的,但是要面试的时候搞出来不容易吧
显不对。dsw好像可以是n的,但是要面试的时候搞出来不容易吧
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的,但是要面试的时候搞出来不容易吧
相关阅读
凳子骑最后选歌就是一个死啊欢迎来湾区,男人的天堂,人生终将辉煌雾霾为出轨出柜者创造了良好的条件啊。。。没人觉得方依依很好看吗?文章内个道歉被扒皮人是铁饭是钢真好看张杰又把郑钧侮辱了一下最近迷上了泰剧一直不喜欢袁珊珊,没有美貌偏要演绝世美女从韩磊唱嫂子颂就觉得他真是大家!【三观不正】一仆二主里的杨树也太ws了吧杨玏硬照大家都是什么办法看那些仅限大陆地区播放的影视剧?请推荐信价比好的看中文电视的盒子尼玛没人讨论马顺家新出的fire tv吗?在听西拉唱Rolling in the deep邓紫棋经纪人张丹讽刺韩磊在《歌手2》总决赛中作弊[通知] TVChinese 主题为<<《我是歌手》第二季冠军花落谁家>>的博彩已开奖张杰对音乐的理解还停留在托儿所的水平吴君如很搞笑啊