将路径序列存储的树转换为name-parent-children层级结构的最高效Python算法

问题描述 #

我们有一个表示树遍历路径的序列：

1 1 2 1 2 3 1 2 3 4 1 5 1 5 6 1 5 6 7 1 5 6 7 8 1 9 1 9 10 1 9 10 11 1 9 10 11 12 1 9 10 13

需要将其转换为name-parent-children格式的嵌套字典结构，最终用于JavaScript程序展示树结构。目标结构示例如下：

[{ "name": "1", "parent": null, "children": [ { "name": "2", "parent": "1", "children": [ { "name": "3", "parent": "2", "children": [ { "name": "4", "parent": "3", "children": [] } ] } ] }, { "name": "5", "parent": "1", "children": [ { "name": "6", "parent": "5", "children": [ { "name": "7", "parent": "6", "children": [ { "name": "8", "parent": "7", "children": [] } ] } ] } ] }, { "name": "9", "parent": "1", "children": [ { "name": "10", "parent": "9", "children": [ { "name": "11", "parent": "10", "children": [ { "name": "12", "parent": "11", "children": [] } ] }, { "name": "13", "parent": "10", "children": [] } ] }, ] } ] }]

高效算法思路 #

要实现最高效的转换，核心思路是利用哈希表（字典）快速查找已创建节点，结合栈跟踪当前路径提取唯一的节点路径，避免重复创建节点：

1. 提取唯一路径：遍历输入序列，用栈维护当前访问的路径，遇到回溯时调整栈结构，将所有唯一的路径存入集合去重。
2. 构建树结构：按路径长度（节点深度）排序，确保父节点先被创建；用字典存储已创建的节点，O(1)时间找到父节点并添加子节点。

Python实现代码 #

import json

def path_sequence_to_tree(path_str):
    # 将输入字符串转换为节点序列列表
    path_sequence = path_str.split()
    
    # 提取所有唯一的完整路径（从根到每个节点的路径）
    unique_paths = set()
    current_stack = []
    
    for node in path_sequence:
        # 调整栈，回到当前节点所在的层级
        while current_stack and current_stack[-1] != node:
            current_stack.pop()
        # 如果当前节点不在栈顶，添加到栈中
        if not current_stack or current_stack[-1] != node:
            current_stack.append(node)
        # 将当前路径（栈）转为元组存入集合（列表不可哈希）
        unique_paths.add(tuple(current_stack))
    
    # 按路径长度排序，确保父节点先被处理；长度相同则按节点名称排序，保证结果顺序和示例一致
    unique_paths = sorted(unique_paths, key=lambda x: (len(x), x[-1]))
    
    # 构建树结构
    node_map = {}
    root = None
    
    for path in unique_paths:
        node_name = path[-1]
        if node_name in node_map:
            continue  # 跳过已创建的节点
        
        # 创建当前节点
        node = {
            "name": node_name,
            "parent": path[-2] if len(path) > 1 else None,
            "children": []
        }
        node_map[node_name] = node
        
        # 处理根节点
        if len(path) == 1:
            root = node
        else:
            # 将当前节点添加到父节点的children列表中
            parent_node = node_map[path[-2]]
            parent_node["children"].append(node)
    
    # 返回JSON格式的树结构（适配JavaScript使用）
    return json.dumps([root], indent=2)

# 输入路径序列
input_sequence = "1 1 2 1 2 3 1 2 3 4 1 5 1 5 6 1 5 6 7 1 5 6 7 8 1 9 1 9 10 1 9 10 11 1 9 10 11 12 1 9 10 13"

# 转换并输出结果
print(path_sequence_to_tree(input_sequence))

代码解释 #

1. 路径提取：通过栈维护当前访问的路径，遇到与栈顶不同的节点时，回溯栈直到找到当前节点的父层级，再将当前节点压入栈，确保每个路径都是从根到当前节点的完整路径，并用集合去重。
2. 树构建：按路径长度排序保证父节点先被创建，哈希表node_map让我们可以在O(1)时间内找到父节点，避免重复遍历查找，大大提升效率。
3. JSON输出：最终将树结构转换为JSON格式，直接可以在JavaScript中使用，无需额外处理。

复杂度分析 #

• 时间复杂度：O(N)，其中N是输入序列的长度。遍历序列提取路径是O(N)，处理唯一路径的总时间也是线性的（所有路径的长度之和与N成正比）。
• 空间复杂度：O(M)，其中M是树中节点的数量。哈希表和栈的空间开销都与节点数量线性相关。

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