从JavaScript中的平面数组构建树数组

从JavaScript中的平面数组构建树数组

如果使用地图查找，则有一个有效的解决方案。如果父母总是先于孩子，则可以合并两个for循环。它支持多个根。它在悬垂的分支上给出错误，但可以修改以忽略它们。它不需要第三方库。据我所知，这是最快的解决方案。

function list_to_tree(list) {    var map = {}, node, roots = [], i;    for (i = 0; i < list.length; i += 1) {        map[list[i].id] = i; // initialize the map        list[i].children = []; // initialize the children    }    for (i = 0; i < list.length; i += 1) {        node = list[i];        if (node.parentId !== "0") { // if you have dangling branches check that map[node.parentId] exists list[map[node.parentId]].children.push(node);        } else { roots.push(node);        }    }    return roots;}var entries = [    {        "id": "12",        "parentId": "0",        "text": "Man",        "level": "1"    }, {  }];console.log(list_to_tree(entries));

如果您对复杂性理论感兴趣，则此解为Θ（n log（n））。递归滤波器的解决方案是Θ（n ^ 2），这对于大数据集可能是个问题。