Python嵌套列表树结构：如何推导指定节点到根的路径

核心思路 #

要反向获取节点到根的路径，关键先把每个节点的父节点信息存成一个"节点-父节点"对照表，之后从目标节点出发，顺着父节点一步步往上找，直到根节点即可。

具体步骤及代码 #

1. 生成父节点映射字典

基于你现有遍历函数改造，不用打印，而是把节点和父节点的对应关系存入字典：

def build_parent_map(node, adj, parent, parent_map):
    # 记录当前节点的父节点
    parent_map[node] = parent
    # 递归遍历子节点
    for cur in adj[node]:
        if cur != parent:
            build_parent_map(cur, adj, node, parent_map)

2. 编写路径查询函数

利用生成的父节点字典，从目标节点往上追溯到根节点（根节点1的父节点是0）：

def get_path_to_root(target_node, parent_map):
    path = []
    current = target_node
    # 循环直到找到根节点的父节点标记（0）
    while current != 0:
        path.append(str(current))
        # 跳到当前节点的父节点
        current = parent_map[current]
    # 把路径列表转为指定格式的字符串
    return " -> ".join(path)

3. 完整使用示例

根据你给出的运行结果，对应的邻接表adj如下，直接代入即可测试：

# 邻接表，adj[节点]存储该节点的所有子节点
adj = {
    1: [2, 3, 4, 5],
    2: [],
    3: [10, 11],
    10: [],
    11: [14,15,16,17,18,19],
    14: [],
    15: [],
    16: [],
    17: [],
    18: [],
    19: [],
    4: [],
    5: []
}

# 构建父节点字典
parent_map = {}
build_parent_map(1, adj, 0, parent_map)

# 查询节点17到根的路径
print(get_path_to_root(17, parent_map))  # 输出：17 -> 11 -> 3 -> 1

代码说明 #

• build_parent_map：递归遍历整棵树，把每个节点的父节点信息存入字典，比如parent_map[17] = 11、parent_map[11] = 3，相当于给每个节点记好"上级是谁"。
• get_path_to_root：从目标节点开始，每次把当前节点加入路径，然后跳到它的父节点，直到碰到根节点的标记（0），最后把路径拼接成要求的格式。

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