SOURCE

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 },
]


// 方式一: 递归方式 时间复杂度为O(2^n)，空间复杂度O(1)
const arrayToTree = (data, pid) => {
    const res = [];
    getChildren(data, res, pid);
    return res;
}

/**
 * 递归 data 获取各项 children 值
 */
const getChildren = (data, res, pid) => {
    for (const item of data) {
        if (item.pid === pid) {
            newItem = { ...item, children: [] };
            res.push(newItem);
            getChildren(data, newItem.children, item.id);
        }
    }
}

// console.log(arrayToTree(arr, 0));


// 方式二（更优解）时间复杂度为O(n)，空间复杂度O(n)
// 把数据转成 Map 去存储，之后遍历的同时借助对象的引用，直接从 Map 找对应的数据做存储。
const arrayToTree2 = (data) => {
    const res = [];
    const itemMap = {}; // 存储

    for (const item of data) {
        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) {
            res.push(treeItem);
        } else {
            if (!itemMap[pid]) {
                itemMap[pid] = {
                    children: []
                }
            }
            itemMap[pid].children.push(treeItem);
        }
    }
    return res;
}

// console.log(arrayToTree2(arr))