JS从扁平array转tree 递归

有时我们需要从扁平的数组结构(flat array)，根据id，和pid构建出树形数组结构(tree array)，这种情形经常出现在嵌套的目录结构，如下图：

文章图片

或者企业的部门架构，也会出现上面的类似结构。

类似上面的情景，假如我们有以下的数据：

let entries = [{ "id": "12", "parentId": "0", "text": "Man", "level": "1", "children": null }, { "id": "7", "parentId": "12", "text": "Other", "level": "2", "children": null }, { "id": "8", "parentId": "7", "text": "Bird", "level": "3", "children": null }, { "id": "9", "parentId": "0", "text": "Woman", "level": "1", "children": null }, { "id": "11", "parentId": "9", "text": "Girl", "level": "2", "children": null } ];

我们期待通过一个算法，构建出下面的结构：

[ { "id": "12", "parentId": "0", "text": "Man", "level": "1", "children": [ { "id": "7", "parentId": "12", "text": "Other", "level": "2", "children": [ { "id": "8", "parentId": "7", "text": "Bird", "level": "3", "children": [] } ] } ] }, { "id": "9", "parentId": "0", "text": "Woman", "level": "1", "children": [ { "id": "11", "parentId": "9", "text": "Girl", "level": "2", "children": [] } ] } ]

也许我们可以想到，在遍历数组的时候使用递归。没错可以解决问题，但是这种方式并不高效。
最近，在Stack Overflow上看到一个方法，感觉不错，贴出来分享一下：

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; }

算法的复杂度是Θ(n log(n))。
【JS从扁平array转tree】如果使用递归，那么复杂度是Θ(n^2)。如果数据集比较大，那么执行的时间会很长。