如何在Golang中将含父字段的扁平对象列表转为嵌套树形结构

我有一组包含ReportTo字段的EmployeeNode结构体扁平数组，需要构建以EmployeeNode为根节点的树形结构，使每个节点的Children字段包含所有向该节点直接汇报的下属列表，下属节点也按此规则嵌套。

结构体定义 #

type EmployeeNode struct {
    UserName string 
    ReportTo string 
    Children []EmployeeNode 
}

输入示例 #

var input []EmployeeNode = []EmployeeNode{
    {
        UserName: "Bob Wang",
        ReportTo: "",
        Children: []EmployeeNode{}
    },
    {
        UserName: "Jim Halpert",
        ReportTo: "Bob Wang",
        Children: []EmployeeNode{}
    },
    {
        UserName: "Brett Wang",
        ReportTo: "Jim Halpert",
        Children: []EmployeeNode{}
    },
    {
        UserName: "Ryan Wang",
        ReportTo: "Jim Halpert",
        Children: []EmployeeNode{},
    },
    {
        UserName: "Michael Wang",
        ReportTo: "Bob Wang",
        Children: []EmployeeNode{}
    },
    {
        UserName: "Annie Wang",
        ReportTo: "Michael Wang",
        Children: []EmployeeNode{}
    }, 
    {
        UserName: "Jay Wang",
        ReportTo: "Michael Wang",
        Children: []EmployeeNode{}
    },
}

期望的根节点结果 #

// Expected result
var root EmployeeNode = EmployeeNode{
    UserName: "Bob Wang",
    ReportTo: "",
    Children: []EmployeeNode{
        EmployeeNode{
            UserName: "Jim Halpert",
            ReportTo: "Bob Wang",
            Children: []EmployeeNode{
                EmployeeNode{
                    UserName: "Brett Wang",
                    ReportTo: "Jim Halpert",
                    Children: []EmployeeNode{},
                },
                EmployeeNode{
                    UserName: "Ryan Wang",
                    ReportTo: "Jim Halpert",
                    Children: []EmployeeNode{},
                },
            }
        },
        EmployeeNode{
            UserName: "Michael Wang",
            ReportTo: "Bob Wang",
            Children: []EmployeeNode{
                EmployeeNode{
                    UserName: "Annie Wang",
                    ReportTo: "Michael Wang",
                    Children: []EmployeeNode{},
                },
                EmployeeNode{
                    UserName: "Jay Wang",
                    ReportTo: "Michael Wang",
                    Children: []EmployeeNode{},
                },
            }
        },
    },
}

实现方案 #

可以借助哈希表（map）快速查找员工节点，高效构建树形结构：

func buildEmployeeTree(employees []EmployeeNode) EmployeeNode {
    // 用map存储所有员工，key为用户名，便于O(1)查找
    empMap := make(map[string]*EmployeeNode)
    var root EmployeeNode

    // 初始化map并定位根节点（ReportTo为空的节点）
    for i := range employees {
        empMap[employees[i].UserName] = &employees[i]
        if employees[i].ReportTo == "" {
            root = employees[i]
        }
    }

    // 遍历所有员工，将每个员工添加到其直属上级的Children列表中
    for _, emp := range employees {
        if emp.ReportTo != "" {
            if supervisor, ok := empMap[emp.ReportTo]; ok {
                supervisor.Children = append(supervisor.Children, emp)
            }
        }
    }

    return root
}

代码说明 #

1. 构建哈希表：先遍历一次数组，把每个员工的指针存入map，同时找到根节点（ReportTo为空的节点）。
2. 填充子节点：再次遍历数组，对每个非根节点，通过map快速找到其直属上级，将当前员工添加到上级的Children列表中。
3. 返回根节点：最后返回构建完成的根节点，此时根节点已包含完整的树形结构。

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