问道G的onsite题

http://www.mitbbs.com//article_t/JobHunting/33056297.html

发信人: austurela (austurela), 信区: JobHunting
标  题: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 02:48:26 2015, 美东)

在别处看到别的公司也考，突然想起来我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
--
※ 修改:·austurela 於 Sep 19 03:42:49 2015 修改本文·[FROM: 98.]