查找混合层级结构中多个子节点首个公共父节点的实现方法咨询

需求说明 #

• 给定树形结构存储的层级关系，输入多个子节点ID，返回它们的最近公共父节点，无公共父节点则返回null
• 业务场景下基于员工岗位层级表计算，目标返回公共所属的Subdivision值

示例参考 #

1. 通用树形结构示例

1       
   / \     
  2   3    
 /   / \
7   8   9  
   / \
 10   11

输入节点[10,9]，输出最近公共父节点3

2. 业务表结构示例

员工岗位层级表字段：EmployeePositionId（岗位ID）、Subdivision（分部ID）、Parent（父分部ID）

+------------------+-----------+------+
|EmployeePositionId|Subdivision|Parent|
+------------------+-----------+------+
|4718              |485        |42    |
|4719              |5064       |485   |
|4720              |5065       |5064  |
|4721              |5065       |5064  |
|4722              |3000       |null  |
+------------------+-----------+------+

• 输入岗位ID列表[4719,4720,4721]，返回5064
• 输入岗位ID列表[4719,4720,4721,4722]，返回null

实现思路 #

• 第一步：构建映射关系。读表后建立两个字典：
  1. pos_map：key为EmployeePositionId，value为对应的Subdivision值，用于快速根据输入的岗位ID查到所属分部
  2. sub_parent_map：key为Subdivision，value为对应的Parent值，用于快速查分部的上级分部
• 第二步：生成每个输入节点的祖先链。对每个输入的岗位ID，先拿到所属分部，再迭代向上查所有父级，生成从当前分部到根节点的全量祖先列表（包含自身）
• 第三步：计算公共祖先。取所有节点祖先链的交集，交集中深度最大（离输入节点最近）的元素即为最近公共父节点；如果交集为空则返回None。

Python实现代码 #

def find_latest_common_subdivision(input_pos_ids, pos_map, sub_parent_map):
    # 1. 获取所有输入节点的祖先链集合
    ancestor_chains = []
    for pos_id in input_pos_ids:
        if pos_id not in pos_map:
            return None
        current_sub = pos_map[pos_id]
        chain = set()
        # 迭代向上找所有祖先
        while current_sub is not None:
            chain.add(current_sub)
            current_sub = sub_parent_map.get(current_sub, None)
        ancestor_chains.append(chain)
    
    # 2. 求所有祖先链的交集
    if not ancestor_chains:
        return None
    common_ancestors = ancestor_chains[0]
    for chain in ancestor_chains[1:]:
        common_ancestors = common_ancestors.intersection(chain)
        if not common_ancestors:
            return None
    
    # 3. 找交集中深度最大的节点
    sample_pos = input_pos_ids[0]
    current_sub = pos_map[sample_pos]
    while current_sub is not None:
        if current_sub in common_ancestors:
            return current_sub
        current_sub = sub_parent_map.get(current_sub, None)
    return None

# 测试用例
if __name__ == "__main__":
    # 模拟从表中读取的映射数据
    pos_map = {
        4718: 485,
        4719: 5064,
        4720: 5065,
        4721: 5065,
        4722: 3000
    }
    sub_parent_map = {
        485: 42,
        5064: 485,
        5065: 5064,
        3000: None
    }
    # 测试1
    print(find_latest_common_subdivision([4719,4720,4721], pos_map, sub_parent_map)) # 输出5064
    # 测试2
    print(find_latest_common_subdivision([4719,4720,4721,4722], pos_map, sub_parent_map)) # 输出None

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