树形结构转垂直列路径式字符串表示的通用算法求解

要实现这种按根到叶子路径列对齐的树形字符串输出，核心是先明确路径顺序与节点上下文，再逐层构建带连接符的输出。以下是高效通用的实现方案，完全无需修改原节点：

核心思路 #

这种布局的本质是将所有根到叶子的路径按左到右顺序排列，同一层的节点在同一行，用连接符关联父子节点。实现分为三个关键阶段：收集路径、预计算节点元数据、逐行构建输出。

步骤1：收集所有根到叶子的路径 #

用深度优先搜索（DFS）遍历树，优先遍历左子节点，每次走到叶子节点（children为空）时，记录完整路径（从根到当前节点的节点列表）。路径顺序直接决定最终列的左右顺序。

示例伪代码：

def collect_paths(node, current_path, paths):
    current_path.append(node)
    if not node.children:
        paths.append(current_path.copy())
    else:
        for child in node.children:
            collect_paths(child, current_path, paths)
    current_path.pop()

步骤2：预计算节点上下文元数据 #

为每个节点记录三个关键信息（存储在外部字典，不修改原节点）：

• is_last_child：是否是父节点的最后一个子节点（决定前缀用└─还是├─）
• has_children：是否有子节点（决定是否需要在节点后绘制连接横线）
• child_count：子节点数量（用于计算横线长度）

示例伪代码：

def compute_node_metadata(node, parent_meta=None, meta_dict=None):
    if meta_dict is None:
        meta_dict = {}
    node_id = id(node)
    meta_dict[node_id] = {
        "is_last_child": node == parent_meta["children"][-1] if parent_meta else False,
        "has_children": len(node.children) > 0,
        "child_count": len(node.children),
        "children": node.children
    }
    for child in node.children:
        compute_node_metadata(child, meta_dict[node_id], meta_dict)
    return meta_dict

步骤3：逐行构建输出字符串 #

从根节点开始，逐层处理每一层的节点、占位符与连接符：

3.1 根节点行 #

直接输出根节点的字符串即可。

3.2 后续层级处理 #

对于每一层（从根的子节点层开始）：

1. 左侧占位符：遍历当前路径左侧的所有路径，若左侧路径仍有未结束的分支（父节点不是最后一个子节点），用│占位，否则用空格，保证竖线连接的连贯性。
2. 节点前缀：根据is_last_child属性，使用└─（最后一个子节点）或├─（非最后子节点）。
3. 节点字符串：直接拼接节点的字符串表示。
4. 后置连接符：若节点有子节点，绘制横线───覆盖所有子节点的列宽度，末尾加┐，确保连接到下一层的子节点位置。

关键细节 #

• 横线长度需根据子节点的总宽度（前缀+字符串长度）计算，确保┐精准对齐最右侧子节点。
• 已结束的路径需用对应长度的空格或│填充，保证列对齐。

示例伪代码（核心行构建逻辑）：

def build_tree_string(root):
    # 收集路径与元数据
    paths = []
    collect_paths(root, [], paths)
    meta_dict = compute_node_metadata(root)
    output = [str(root)]
    max_depth = max(len(p) for p in paths)

    for depth in range(1, max_depth):
        line_parts = []
        for path_idx, path in enumerate(paths):
            if len(path) <= depth:
                # 路径已结束，判断是否需要竖线占位
                has_active_branch = False
                for d in range(depth):
                    if d >= len(path):
                        continue
                    node = path[d]
                    if not meta_dict[id(node)]["is_last_child"]:
                        has_active_branch = True
                        break
                # 填充对应宽度（前缀+节点长度）
                fill_width = 2 + len(str(path[-1]))
                line_parts.append("│" * fill_width if has_active_branch else " " * fill_width)
                continue

            current_node = path[depth]
            parent_node = path[depth-1]
            current_meta = meta_dict[id(current_node)]
            parent_meta = meta_dict[id(parent_node)]

            # 处理左侧路径的占位符
            left_fill = []
            for prev_path in paths[:path_idx]:
                if len(prev_path) <= depth:
                    # 检查左侧路径是否有活跃分支
                    prev_active = False
                    for d in range(depth):
                        if d >= len(prev_path):
                            continue
                        if not meta_dict[id(prev_path[d])]["is_last_child"]:
                            prev_active = True
                            break
                    left_fill.append("│" if prev_active else " ")
                else:
                    # 填充左侧节点的宽度
                    prev_node_len = 2 + len(str(prev_path[depth]))
                    left_fill.append(" " * prev_node_len)
            line_parts.append("".join(left_fill))

            # 添加节点前缀与字符串
            prefix = "└─" if current_meta["is_last_child"] else "├─"
            line_parts.append(prefix)
            line_parts.append(str(current_node))

            # 添加后置连接横线
            if current_meta["has_children"]:
                # 计算子节点总宽度
                total_child_width = sum(2 + len(str(child)) for child in current_node.children)
                dash_length = total_child_width - len(str(current_node)) - 1  # 减去┐的宽度
                line_parts.append("─" * dash_length + "┐")

        # 合并并清理当前行
        current_line = "".join(line_parts).rstrip()
        output.append(current_line)

    return "\n".join(output)

优化与适配 #

• 时间效率：整体时间复杂度为O(N + M*K)，其中N是节点总数，M是路径数量，K是树的最大深度，属于线性高效算法。
• 长字符串适配：通过动态计算节点长度与横线长度，自动适配长节点名的对齐需求。
• 无节点修改：所有元数据存储在外部字典，完全不影响原节点结构。

内容的提问来源于stack exchange，提问作者Gigi Bayte 2