|
|---|
|
|
|
|
|
|
e*****e
发帖数: 1275 | 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******7
发帖数: 1728 | 2 都得一个节点一个节点的删除吧？O1？ 没有思路。等高人 | l******l
发帖数: 66 | 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*****u
发帖数: 1133 | 4 如果把binary tree转成double linked list的话，时间是O(nlogn)肯定可以，时间O(n
)空间constant的还没想到。
假设树是满的，要么用logn的辅助空间暂存node，要么用logn的时间去找到没有或只有
一个child的node。是不是有什么tricky的办法？ | l******l
发帖数: 66 | | j*****u
发帖数: 1133 | 6 NICE solution!
【在 l******l 的大作中提到】
: Given:
: 1
: 2 3
: 4 5 6 7
|
|
|
|
|
|
|
|
