Pinterest ParentIndex Forest：删子树并稳定压紧索引

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入确实是 forest：-1 表示原始根，其他 parentIndex 是有效索引，且无环；目标索引有效。
• 原始根本来也是 -1，故“标成 -1”的第一问输出不能单独区分已删节点和原始根；实现内部保留 removed 布尔集合。
• 第二问幸存节点保持原始索引相对顺序，返回有效前缀长度；补齐的 -1 是填充区，不属于有效 forest。

解题路线

1. 先扫描 parentIndex 构造 parent→children 邻接表，这样从 target DFS 能访问全部子孙，而不必对每个节点往上追祖先。
2. 用独立 removed 数组记录删除集合；第一问的 marked 数组只是要求的展示形式，不能拿其中的 -1 判断谁被删。
3. 从左到右扫描幸存旧节点，建立 oldIndex→newIndex；再次按旧索引顺序输出新 parentIndex，原根仍为 -1，非根改成其父的 newIndex。
4. 若输入是合法 forest，幸存节点的父不会被删除而自己幸存；删除目标子树保证了这一点。最后尾部补 -1。

手动走一遍

parent=[-1,0,0,1,1,2]，target=1，删掉 1、3、4，marked=[-1,-1,0,-1,-1,2]。幸存旧索引 [0,2,5]→新索引 [0,1,2]，有效 parent 前缀 [-1,0,1]，完整压紧数组 [-1,0,1,-1,-1,-1]。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Delete target descendants in a parent-index forest and compact survivors."""


def delete_and_compact(parent: list[int], target: int):
    count = len(parent)
    if not 0 <= target < count:
        raise ValueError("target is out of range")
    children = [[] for _ in parent]
    for child, ancestor in enumerate(parent):
        if ancestor == -1:
            continue
        if not 0 <= ancestor < count or ancestor == child:
            raise ValueError("invalid parent index")
        children[ancestor].append(child)
    removed = [False] * count
    stack = [target]
    while stack:
        node = stack.pop()
        if removed[node]:
            continue
        removed[node] = True
        stack.extend(children[node])
    marked = [-1 if removed[index] else ancestor for index, ancestor in enumerate(parent)]
    old_to_new = {}
    for old_index in range(count):
        if not removed[old_index]:
            old_to_new[old_index] = len(old_to_new)
    compacted = []
    for old_index, ancestor in enumerate(parent):
        if removed[old_index]:
            continue
        compacted.append(-1 if ancestor == -1 else old_to_new[ancestor])
    survivors = len(compacted)
    compacted.extend([-1] * (count - survivors))
    return marked, compacted, survivors

复杂度

建 children、DFS、两次稳定扫描均 O(N) 时间；邻接表、removed 和映射 O(N) 空间。若严格要求 O(1) 额外空间，题目未明确该限制，需要重新讨论原地重排与父映射。

易错点与追问

容易失分的边界

• 用 marked 中的 -1 判断删除，误删所有原始根。
• 压紧节点后沿用旧 parentIndex，指向错误位置。
• 按 DFS 访问顺序输出幸存节点，破坏稳定顺序。
• 以为删掉一个父节点后子节点仍可保留。

继续深挖

• 若 forest 输入可能有环，应如何检测并报告？
• 若一次删除多个 target，如何避免重复遍历？
• 如果节点有独立 ID，是否仍需重写 parent index？