请教一个问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一个问题

请教一个问题# JobHunting - 待字闺中

e*e2011-02-18 08:02

1 楼

Given a BST in a language where memory must be handled manually, how do you
completely remove BST from memory? Recursion is not allowed. Was later told
that desired solution had O(N) time and O(1) space. ??????
实在是想不出不要 recursion O(1) 的办法

H*72011-02-18 08:02

2 楼

都得一个节点一个节点的删除吧？O1？没有思路。等高人

l*l2011-02-18 08:02

3 楼

Just a thought:
1. Restructure the binary tree (tree rotation) such that only root has two childern, other
nodes each has only one child. I think this can be done in
O(N).
2. Repeat root deleting. O(N).

j*u2011-02-18 08:02

4 楼

如果把binary tree转成double linked list的话，时间是O(nlogn)肯定可以，时间O(n
)空间constant的还没想到。
假设树是满的，要么用logn的辅助空间暂存node，要么用logn的时间去找到没有或只有
一个child的node。是不是有什么tricky的办法？

l*l2011-02-18 08:02

5 楼

Given:
1
2 3
4 5 6 7

j*u2011-02-18 08:02

6 楼

NICE solution!

【在 l******l 的大作中提到】