遍历父子ID映射字典查询指定ID是否存在特定祖先的实现问题

问题分析 #

• 核心需求：对字典中每个ID，向上遍历父节点链路，判断是否存在指定祖先节点，匹配成功则将原始ID存入结果列表
• 原代码存在的问题：
  • 冗余嵌套了for i in d循环，不需要遍历全字典，只要顺着当前ID的父节点链路逐次向上查询即可
  • 未处理父节点不存在于字典key的边界情况，会触发死循环（比如ID7的父节点是10，10不在字典key中，y !=3的判断永远成立）
  • 未做匹配成功的判断就直接追加ID到列表，会混入不符合要求的结果

实现代码 #

# 存储符合条件的ID
result = []
# 父子关系字典
d = {
     1: 2,
     2: 3,
     3: 4,
     4: 5,
     7: 10,
     99: 3,
     26: 8,
     9: 26
}
# 指定要匹配的目标祖先ID
target_ancestor = 3

def has_target_ancestor(current_id, target, parent_map):
    # 循环向上回溯父节点
    while current_id in parent_map:
        # 取当前ID的父节点
        parent_id = parent_map[current_id]
        # 匹配到目标祖先直接返回True
        if parent_id == target:
            return True
        # 没匹配到就把父节点设为当前节点，继续向上找
        current_id = parent_id
    # 到顶还没找到，返回False
    return False

# 遍历所有待检查的ID
for id in d:
    if has_target_ancestor(id, target_ancestor, d):
        result.append(id)

print(result)
# 输出结果：[1, 2, 99]

逻辑说明 #

1. 单独封装判断函数has_target_ancestor，入参为待检查的ID、目标祖先ID、父子映射字典，返回布尔值表示是否匹配
2. 回溯逻辑：
   • 只要当前ID在字典中存在父节点，就持续向上查询
   • 每拿到一个父节点就和目标祖先比对，匹配成功直接返回结果
   • 如果当前ID没有父节点（不在字典的key里），说明已经遍历到链路顶端，匹配失败返回
3. 遍历所有待检查的ID，只有判断返回True的才加入结果列表

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