问道G的onsite题

原帖地址:mitbbs

在别处看到别的公司也考,突然想起来我G onsite貌似挂在这题上了。想请教请教各位
大牛怎么做

“给你一棵树,不是binary的,每个节点会有任意个children,然后这棵树是存在一个
数组里的,数组的每个元素就是一个节点,节点包含了它的index以及它的parent的
index,而不是children的index哦,所以这棵树是从child指向parent的。最后是给我
这个数组和一个节点的index,让我删除这个index以及它的子树,只能用O(n)的空间复
杂度,而且大小是确定好的”
数组里各个node是打乱的,不是topologically sorted的

update:
举个例子:
[3,1,4,1,5,7,2,6]
删index 1
得到
[x,x,4,x,5,7,2,6] (x代表被删除)
最终输出
[1,2,4,0,3]

我觉得主要难点在找到哪些index要删,最后往前挪补空缺的步骤比较trivial