构建路径字符串的树形结构：Go 语言高效实现教程-Golang-PHP中文网

构建路径字符串的树形结构：Go 语言高效实现教程

本文详解如何将一组路径字符串（如 "a/b/c"）合并构建成嵌套的 JSON 可序列化树形结构，使用递归与节点查找避免重复、支持多路径合并，并给出完整可运行的 Go 实现。

本文详解如何将一组路径字符串（如 `"a/b/c"`）合并构建成嵌套的 json 可序列化树形结构，使用递归与节点查找避免重复、支持多路径合并，并给出完整可运行的 go 实现。

在 Go 中将扁平路径（如 "a/b/c"、"a/b/g"、"a/d"）构建成层次化的树形结构，是文件系统建模、路由注册、配置解析等场景的常见需求。核心挑战在于：既要复用已有节点（如 a 和 b），又要精准插入新分支（如 g），同时避免因指针误用或逻辑错误导致节点污染或重复。

关键设计原则有三点：
✅ 以切片为操作单元：不固定单根节点，而是对 []Node 进行递归构建，天然支持多根路径（如同时含 "x/y" 和 "a/b"）；
✅ 显式查找 + 按需创建：每次递归前遍历当前层级子节点，若已存在同名节点则复用，否则追加新节点；
✅ 绝不复用输入节点内容：每次插入都新建 Node 实例，避免 Name 被意外覆盖、Children 被错误共享（原问题中 appendChild 直接修改入参 root 是典型陷阱）。

以下是推荐实现：

type Node struct {
    Name     string `json:"name"`
    Children []Node `json:"children,omitempty"` // omitempty 避免空数组输出 null
}

// AddToTree 将路径切片（如 ["a","b","c"]）插入到 root 切片中，返回更新后的 root
func AddToTree(root []Node, names []string) []Node {
    if len(names) == 0 {
        return root
    }

    // 在当前层级查找是否存在同名节点
    var i int
    for i = 0; i  0 && parts[0] != "" { // 过滤空路径
            root = AddToTree(root, parts)
        }
    }
    return root
}

使用示例：

func main() {
    paths := []string{
        "a/b/c",
        "a/b/g",
        "a/d",
    }

    tree := BuildTree(paths)
    data, _ := json.MarshalIndent(tree, "", "  ")
    fmt.Println(string(data))
}

输出（符合预期）：

[
  {
    "name": "a",
    "children": [
      {
        "name": "b",
        "children": [
          { "name": "c" },
          { "name": "g" }
        ]
      },
      { "name": "d" }
    ]
  }
]

⚠️ 注意事项：

路径分隔符 / 可按需替换（如 Windows 路径用 \，或 URL 路由用 /）；
若需支持绝对路径（如 "/a/b"），建议预处理 strings.TrimPrefix(path, "/")；
Children 字段使用 omitempty 标签后，空切片将被忽略（JSON 中不出现 "children":[]），更简洁；若需显式保留空数组，移除此标签即可；
该算法时间复杂度为 O(n·m)（n 为总路径段数，m 为平均树宽），对万级路径仍高效；如需极致性能（如百万路径），可改用 map[string]*Node 加速查找。