Java泛型树遍历与节点过滤：保留指定叶子并清理空子树

没问题，我来帮你搞定这个树结构的过滤需求！核心思路是从叶子节点反向向上遍历，先处理不符合保留条件的叶子，再逐层检查父节点是否因为所有子节点被删除而变成空树，进而递归删除。下面是具体的实现步骤和代码示例：

核心思路拆解 #

• 反向映射构建：先建立子节点到父节点的映射，这样删除叶子后能快速找到其父节点并更新子列表。
• 初始叶子识别：找出所有没有子节点的节点（也就是不在HashMap键中的节点，因为HashMap的键都是有子节点的父ID）。
• 叶子过滤：把不在保留列表里的叶子标记为待删除。
• 向上递归清理：对于每个被删除的节点，检查其父节点的子列表，如果父节点的所有子节点都被删除，那么这个父节点也需要被删除，继续向上递归处理。
• 结果树生成：最后移除所有子列表为空的父节点，得到最终的结果树。

Python代码实现 #

def filter_tree(original_tree, keep_leaves):
    # 1. 构建子节点到父节点的映射（统一节点ID为字符串，避免类型冲突）
    child_to_parent = {}
    for parent_id, children in original_tree.items():
        for child in children:
            child_to_parent[str(child)] = parent_id
    
    # 2. 找出所有初始叶子节点（没有子节点的节点，即不在original_tree的键中）
    all_nodes = set()
    for parent in original_tree:
        all_nodes.add(parent)
        all_nodes.update(map(str, original_tree[parent]))
    initial_leaves = [node for node in all_nodes if node not in original_tree]
    
    # 3. 标记需要删除的叶子节点
    to_delete = set()
    for leaf in initial_leaves:
        if leaf not in map(str, keep_leaves):
            to_delete.add(leaf)
    
    # 4. 向上递归处理父节点，清理空的子树
    processed_nodes = set()
    while to_delete:
        current_node = to_delete.pop()
        if current_node in processed_nodes:
            continue
        processed_nodes.add(current_node)
        
        # 获取当前节点的父节点
        parent_id = child_to_parent.get(current_node)
        if not parent_id:  # 根节点没有父节点，跳过
            continue
        
        # 从父节点的子列表中移除当前节点
        updated_children = [child for child in original_tree[parent_id] if str(child) != current_node]
        original_tree[parent_id] = updated_children
        
        # 如果父节点的子列表为空，加入待删除队列
        if not updated_children:
            to_delete.add(parent_id)
    
    # 5. 生成最终结果树，移除子列表为空的父节点
    result_tree = {}
    for parent_id, children in original_tree.items():
        if children:
            result_tree[parent_id] = children
    
    return result_tree

示例测试 #

假设我们的原始树结构如下（根节点父ID为空字符串）：

original_tree = {
    "": [1, 2],
    "1": [3, 4],
    "2": [5],
    "5": [6, 7]
}
keep_leaves = {4, 6}  # 需要保留的叶子节点

调用函数后：

filtered_tree = filter_tree(original_tree, keep_leaves)
print(filtered_tree)

输出结果：

{'': [1, 2], '1': [4], '2': [5], '5': [6]}

这个结果符合预期：

• 叶子3、7不在保留列表，被删除。
• 节点1因为还有子节点4，所以保留；节点5因为还有子节点6，所以保留。
• 根节点的子节点1和2都存在，所以保留。

注意事项 #

• 节点ID的类型：代码中统一将节点ID转为字符串处理，避免数字和字符串类型不匹配的问题，如果你的节点ID都是同一类型，可以去掉类型转换部分。
• 原数据修改：代码中直接修改了传入的original_tree，如果需要保留原数据，可以先创建一个副本再处理。

内容的提问来源于stack exchange，提问作者clementino