Swift中如何按parentId将对象数组构建为树形结构？

问题背景 #

我们需要将包含id、name、parentId、children属性的MyObject扁平数组转换为树形结构——parentId为nil的对象作为根节点，子节点通过parentId关联到对应父节点。现有实现存在顺序不稳定问题，同时需要适配大数据量的高效处理。

先明确MyObject类定义 #

假设MyObject为引用类型（若为值类型需调整逻辑）：

class MyObject {
    let id: String
    var name: String
    let parentId: String?
    var children: [MyObject] = []
    
    init(id: String, name: String, parentId: String?) {
        self.id = id
        self.name = name
        self.parentId = parentId
    }
}

高效且顺序稳定的实现方案 #

核心思路 #

1. 哈希表快速映射：用字典存储id到MyObject的映射，实现O(1)时间复杂度的父节点查找，避免嵌套遍历的O(n²)低效，适配大数据量场景。
2. 严格保留原始顺序：遍历原始数组时，按输入顺序将子节点添加到父节点的children数组，同时按相同顺序收集根节点，确保最终树形结构的节点顺序与输入完全一致。

实现代码 #

func buildTree(from objects: [MyObject]) -> [MyObject] {
    // 构建id到对象的映射字典，O(n)时间复杂度
    var objectMap: [String: MyObject] = [:]
    for obj in objects {
        objectMap[obj.id] = obj
    }
    
    var rootObjects: [MyObject] = []
    
    // 按原始数组顺序关联父子节点，O(n)时间复杂度
    for obj in objects {
        if let parentId = obj.parentId, let parentObj = objectMap[parentId] {
            // 严格遵循输入顺序添加子节点，保证顺序稳定
            parentObj.children.append(obj)
        } else {
            // 收集根节点，同样遵循输入顺序
            rootObjects.append(obj)
        }
    }
    
    return rootObjects
}

方案优势 #

• 性能高效：仅需两次线性遍历，哈希表查找为O(1)，整体时间复杂度为O(n)，处理10w+级别的大数据量时，性能远优于嵌套遍历的实现。
• 顺序稳定：完全按照输入数组的遍历顺序构建树形结构，根节点和子节点的顺序均与输入一致。
• 空间合理：空间复杂度为O(n)，主要消耗在哈希表存储，属于典型的空间换时间的高效方案。

注意事项 #

• 若MyObject是值类型（struct），需改为引用类型（class），或在字典中存储数组索引（值类型会被复制，修改副本无法同步到原对象）。
• 确保输入数组中的id唯一，避免字典键冲突导致的对象覆盖；若存在重复id，需提前校验数据合法性。

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