如何在构建祖先树时检测无限循环且保留合法重复节点场景

核心逻辑为放弃全局已访问节点校验，改为仅校验当前递归链路内的节点重复，具体实现方案如下：

• 递归函数新增入参存储当前遍历链路的人员ID集合，该集合仅包含从初始节点到当前递归节点的完整路径上的所有节点ID
• 每次处理新的父节点前，先校验该父节点ID是否存在于当前链路集合中：
  • 存在则判定为循环引用，终止当前分支的递归遍历，可同步记录异常数据信息用于后续修正
  • 不存在则拷贝当前链路集合，将该父节点ID加入拷贝后的集合后，继续向上递归查询父节点的祖先
• 不同分支的递归调用使用独立的链路集合副本，互相无干扰，天然支持同一人员出现在不同独立分支的合法场景

参考实现代码（Python伪代码） #

def build_ancestor_tree(node_id, current_path=None):
    # 初始化当前路径集合
    if current_path is None:
        current_path = set()
    # 检测循环
    if node_id in current_path:
        return {"id": node_id, "error": "存在循环引用，终止该分支遍历"}
    # 生成新的路径集合传入下一层递归
    new_path = current_path.copy()
    new_path.add(node_id)
    # 从数据源查询当前节点的父节点列表
    parent_ids = query_parent_ids(node_id)
    node_data = {"id": node_id, "ancestors": []}
    for pid in parent_ids:
        node_data["ancestors"].append(build_ancestor_tree(pid, new_path))
    return node_data

优化建议 #

• 若需要输出完整循环链路用于排查错误，可将current_path替换为有序列表，检测到重复时可直接输出全链路的节点顺序
• 节点量较大时，使用哈希集合存储路径ID可保证校验操作时间复杂度为O(1)，不会产生明显性能损耗

内容的提问来源于stack exchange，提问作者Mårten Swärd