扁平数据结构转Tree

let arr = [
    {id: 1, name: '部门1', pid: 0},
    {id: 2, name: '部门2', pid: 1},
    {id: 3, name: '部门3', pid: 1},
    {id: 6, name: '部门3', pid: 2},
    {id: 4, name: '部门4', pid: 3},
    {id: 7, name: '部门4', pid: 3},
    {id: 5, name: '部门5', pid: 4},
]

自己写的方法，使用递归方式

//第一步选取根结点
const getData = arr.filter(v => !arr.some((item) => item.id === v.pid))
let length = getData.length
// 递归循环处理数据
function returnData(result, pid){
    arr.filter( val=>{
        if(val.pid!=result.pid) {
            if (pid == val.pid) {
                if (!result.children) {
                    result.children = []
                }
                result.children.push(val)
                length++
                if(length<=arr.length){
                    returnData(val, val.id)
                }
            }
        }
    })
}
getData.filter(item=>{
    returnData(item,item.id)
})

网上借鉴的方法（该实现的时间复杂度为O(2n)）

function arrayToTree(items) {
    const result = [];   // 存放结果集
    const itemMap = {};  //
    // 先转成map存储
    for (const item of items) {
        itemMap[item.id] = {...item, children: []}
    }
    for (const item of items) {
        const id = item.id;
        const pid = item.pid;
        const treeItem =  itemMap[id];
        if (pid === 0) {
            result.push(treeItem);
        } else {
            if (!itemMap[pid]) {
                itemMap[pid] = {
                    children: [],
                }
            }
            itemMap[pid].children.push(treeItem)
        }
    }
    return result;
}

网上借鉴的方法（该实现的时间复杂度为O(n)）

function arrayToTree1(items) {
    const result = [];   // 存放结果集
    const itemMap = {};  //
    for (const item of items) {
        const id = item.id;
        const pid = item.pid;

        if (!itemMap[id]) {
            itemMap[id] = {
                children: [],
            }
        }

        itemMap[id] = {
            ...item,
            children: itemMap[id]['children']
        }

        const treeItem =  itemMap[id];

        if (pid === 0) {
            result.push(treeItem);
        } else {
            if (!itemMap[pid]) {
                itemMap[pid] = {
                    children: [],
                }
            }
            itemMap[pid].children.push(treeItem)
        }

    }
    return result;
}