Python中如何从节点深度、名称列表生成各节点完整路径？

实现思路 #

给定的depth和nodeName是树的前序遍历结果，depth对应每个节点的层级，我们可以通过维护一个路径栈实现全路径生成，逻辑如下：

• 遍历节点时，先弹出栈中元素直到栈的长度等于当前节点的深度，保证栈中始终存储当前节点的父级路径
• 将当前节点名压入栈
• 若当前节点是最后一个节点，或下一个节点的深度小于等于当前节点深度，说明当前节点是叶子节点，此时栈中元素拼接即为该叶子节点的完整路径

代码实现 #

data = {
    'depth': [0, 1, 1, 2, 3, 3, 3, 1, 1, 2, 3],
    'nodeName': ['root', 'Deleted Customers', 'New Customers', 'Region', 'Europe', 'Asia', 'America', 'Deleted Partners', 'New Partners', 'Region', 'Europe']
}

path_stack = []
full_paths = []

for idx, (curr_depth, node_name) in enumerate(zip(data['depth'], data['nodeName'])):
    # 对齐路径栈到当前节点深度
    while len(path_stack) > curr_depth:
        path_stack.pop()
    path_stack.append(node_name)
    
    # 判断是否为叶子节点，是则生成全路径
    if idx == len(data['depth']) - 1 or data['depth'][idx + 1] <= curr_depth:
        full_paths.append('\\'.join(path_stack))

# 打印结果
for p in full_paths:
    print(p)

输出验证 #

运行上述代码将直接得到你需要的结果：

root\Deleted Customers
root\New Customers\Region\Europe
root\New Customers\Region\Asia
root\New Customers\Region\America
root\Deleted Partners
root\New Partners\Region\Europe

该方案时间复杂度为O(n)，每个节点最多入栈、出栈一次，无需额外引入第三方库构建树结构，代码简洁高效，符合Pythonic编码规范。

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