扁平数组转树形结构 O(n²)与O(n)时间复杂度方案的实现

/* 
    let arr = [
        { id: 1, name: '部门1', pid: 0 },
        { id: 2, name: '部门2', pid: 1 },
        { id: 3, name: '部门3', pid: 1 },
        { id: 4, name: '部门4', pid: 3 },
        { id: 5, name: '部门5', pid: 4 },
        { id: 6, name: '部门6', pid: 4666 },
    ]
    
    输出结果:
        [
            {
                "id": 1,
                "name": "部门1",
                "pid": 0,
                "children": [
                    {
                        "id": 2,
                        "name": "部门2",
                        "pid": 1,
                        "children": []
                    },
                    {
                        "id": 3,
                        "name": "部门3",
                        "pid": 1,
                        "children": [
                            // 结果 ,,,
                        ]
                    }
                ]
            },
            {
                id: 6,
                name: '部门6',
                pid: 4666
            }
        ]

*/

/* 
    方案1 递归方式 
         先找出所有根节点，再找出所有根节点的子节点
         时间复杂度： O(n²)
*/
const getChildren = root => {
    root.children = arr.filter(v => v.pid === root.id)
    root.children.forEach(v => getChildren(v))
}
const transferTree = arr => {
    if (!Array.isArray(arr)) throw new Error('parameter arr must be Array.')
    if (arr.length === 1) return arr

    // 父子关系可以用map存储
    const idMap = arr.reduce((total, cur) => Object.assign(total, { [cur.id]: { ...cur, children: [] } }), {})

    // 找出所有根节点
    const roots = arr.filter(node => !idMap[node.pid])

    // 找出根节点下面所有子节点
    roots.forEach(root => getChildren(root))

    return roots
}



/* 
    方案2 非递归方式
    时间复杂度： O(n)
*/
const transferTree2 = arr => {
    if (!Array.isArray(arr)) throw new Error('parameter arr must be Array.')
    if (arr.length === 1) return arr

    const res = []
    const idMap = arr.reduce((total, cur) => Object.assign(total, { [cur.id]: { ...cur, children: [] } }), {})
    for (const [, node] of Object.entries(idMap)) {
        // 根节点
        if (idMap[node.pid]) {
            res.push(node)
            continue;
        }
        // 子节点
        idMap[node.pid].children.push(node)
    }

    return res
}


console.log(transferTree2(arr))