基于父数组表示的二叉树：删除指定节点及其所有子节点（无树结构）

嘿，我来帮你搞定这个问题！首先得明确咱们手里的父数组规则：数组的每个索引代表一个节点的编号，对应的值就是这个节点的父节点编号。比如你给的array = [-1, 0, 0, 1, 2, 1, 3, 5, 5, 6, 6]，索引0是根节点（父节点是-1，代表没有父节点），索引1的父是0，索引3的父是1，以此类推。

咱们的目标很明确：删除节点1（也就是数组里索引为1的元素），还要把所有父节点是1的节点（也就是数组里值为1的元素对应的索引）都删掉，同时记录所有被删除的索引，全程不用任何树数据结构。

具体实现步骤 #

第一步：找出所有要删除的索引

首先得把所有需要删掉的节点索引列出来：

• 首先是目标节点本身：索引1
• 然后是所有直接以节点1为父的节点：遍历整个数组，找出所有值等于1的元素的索引——也就是索引3和5（对应节点3和节点5）

所以咱们要删除的索引集合就是{1, 3, 5}

第二步：安全删除元素（避免索引偏移）

这里要注意一个坑：如果直接按从小到大的顺序删除索引，比如先删1，那后面的元素都会往前挪一位，原来的索引3就变成了2，这时候再删3就会删错元素。所以一定要按从大到小的顺序删除，这样前面的元素删除不会影响后面要删的索引位置。

用Python实现的代码示例 #

def delete_target_node(parent_array, target_node):
    # 用集合存要删除的索引，避免重复
    to_delete = set()
    # 先加入目标节点本身的索引
    to_delete.add(target_node)
    
    # 遍历数组，找出所有父节点是target_node的索引
    for idx, parent in enumerate(parent_array):
        if parent == target_node:
            to_delete.add(idx)
    
    # 把索引倒序排序，防止删除时索引偏移
    sorted_delete_indices = sorted(to_delete, reverse=True)
    
    deleted_indices = []
    # 复制原数组，别直接改原数组
    new_array = parent_array.copy()
    
    for idx in sorted_delete_indices:
        deleted_indices.append(idx)
        del new_array[idx]
    
    return new_array, deleted_indices

# 测试咱们的例子
original_array = [-1, 0, 0, 1, 2, 1, 3, 5, 5, 6, 6]
target = 1
result_array, deleted = delete_target_node(original_array, target)

print("原数组:", original_array)
print("被删除的索引（按升序排列）:", sorted(deleted))
print("删除后的数组:", result_array)

代码运行结果 #

原数组: [-1, 0, 0, 1, 2, 1, 3, 5, 5, 6, 6]
被删除的索引（按升序排列）: [1, 3, 5]
删除后的数组: [-1, 0, 2, 3, 5, 5, 6, 6]

扩展：如果要删除节点及其所有后代（包括子节点的子节点） #

如果你的需求是删除节点1以及它的所有后代（比如节点3、5、6、7、8、9、10），那可以稍微调整逻辑，循环找出所有后代节点：

def delete_node_and_all_descendants(parent_array, target_node):
    to_delete = set()
    to_delete.add(target_node)
    
    # 循环找出所有后代节点
    while True:
        new_descendants = set()
        for idx, parent in enumerate(parent_array):
            # 如果当前节点的父在要删除的集合里，且本身还没被标记删除
            if parent in to_delete and idx not in to_delete:
                new_descendants.add(idx)
        # 没有新的后代就退出循环
        if not new_descendants:
            break
        to_delete.update(new_descendants)
    
    # 同样倒序删除
    sorted_delete_indices = sorted(to_delete, reverse=True)
    deleted_indices = []
    new_array = parent_array.copy()
    
    for idx in sorted_delete_indices:
        deleted_indices.append(idx)
        del new_array[idx]
    
    return new_array, deleted_indices

# 测试扩展功能
original_array = [-1, 0, 0, 1, 2, 1, 3, 5, 5, 6, 6]
target = 1
result_array, deleted = delete_node_and_all_descendants(original_array, target)

print("被删除的索引（按升序排列）:", sorted(deleted))
print("删除后的数组:", result_array)

运行结果：

被删除的索引（按升序排列）: [1, 3, 5, 6, 7, 8, 9, 10]
删除后的数组: [-1, 0, 2]

这个版本就完全删除了节点1的整个子树，适合需要彻底移除某节点及其所有后代的场景。

内容的提问来源于stack exchange，提问作者Yuki.kuroshita