这个问题建立在许多类似的问题之上，例如 https://stackoverflow.com/questions/22367711/construct-hierarchy-tree-from-flat-list-with-parent-field/22367819?noredirect=1#comment127716528_22367819
然而，扭曲是没有父ID。例如
[
{id: 1, depth: 1, ...},
{id: 2, depth: 2, ...},
{id: 3, depth: 3, ...},
{id: 4, depth: 2, ...},
{id: 5, depth: 1, ...},
{id: 6, depth: 2, ...},
{id: 7, depth: 2, ...},
{id: 8, depth: 1, ...},
{id: 9, depth: 2, ...},
{id: 10, depth: 3, ...},
{id: 11, depth: 3, ...},
]构造以下 tree 的高效方法是什么？请注意，孩子总是在父母之后，即可以从 depth value 中看到 tree。例如，id 2 是 id 1 的子级，因为它的深度是 2，而 id 1 的深度是 1。id 3 是 id 2 的子级，因为 id 3 的深度是 3。id 4 是 id 1 而不是 id 3 的子级，因为 id 4 的深度是 id 3 的深度 3 的深度为 2（上一步）
\\tree digram
1
2
3
4
5
6
7
8
9
10
11应该有 values 喜欢
[
{id:1, depth:1, children: [
{id: 2, depth: 2, children: [...]},
...
]},
{id:5, depth:1, children: [...]},
{id:6, depth:1, children: [...]},
]回答1
您可以为此使用一个数组，该数组具有每个深度的索引。每时每刻，它将代表从（虚拟）根到当前节点的路径。当处理一个节点时，它的父节点将位于索引 depth-1，它可以插入到该父节点的 children 属性中，并且节点本身将被放置在索引 depth 中：
function createForest(flatdata) {
const path = [{ children: [] }];
for (const obj of flatdata) {
path[obj.depth - 1].children.push(path[obj.depth] = { ...obj, children: [] });
}
return path[0].children;
}
// demo
const flatdata = [{id: 1, depth: 1},{id: 2, depth: 2},{id: 3, depth: 3},{id: 4, depth: 2},{id: 5, depth: 1},{id: 6, depth: 2},{id: 7, depth: 2},{id: 8, depth: 1},{id: 9, depth: 2},{id: 10, depth: 3},{id: 11, depth: 3}];
const roots = createForest(flatdata);
console.log(roots);不规则深度
如果 depth values 不对应节点的实际深度，而是留有间隙，则使用“字典”（普通对象）记录 depth 属性 values 的映射关系它们对应的深度：
function createForest(flatdata) {
const path = [{ children: [] }];
const depthMap = { 0: 0 };
for (const obj of flatdata) {
path[(depthMap[obj.depth] ??= path.length) - 1].children.push(
path[depthMap[obj.depth]] = { ...obj, children: []}
);
}
return path[0].children;
}
// demo
const flatdata = [{id: 1, depth: 10},{id: 2, depth: 20},{id: 3, depth: 30},{id: 4, depth: 20},{id: 5, depth: 10},{id: 6, depth: 20},{id: 7, depth: 20},{id: 8, depth: 10},{id: 9, depth: 20},{id: 10, depth: 30},{id: 11, depth: 30}];
const roots = createForest(flatdata);
console.log(roots);然而，如果唯一的不规则是深度并不总是从 1 开始，有时从 2 开始，那么在输入数据前加上一个虚拟的 depth-one 节点，使用第一个函数，然后删除虚拟节点会更有效结果中的“根”（深度为 1）。
回答2
遍历数组并将每个项目添加到 tree 以及一系列面包屑。每个下一个项目要么作为一个孩子进入最后一个，要么通过面包屑路径回溯到需要插入它的正确深度：
const peek = arr =>
arr[arr.length-1];
function toTree(arr) {
const tree = [];
const trail = [];
for (const item of arr) {
while ((peek(trail)?.depth ?? 0) >= item.depth) {
trail.pop();
}
const current = peek(trail)?.children ?? tree;
const treeNode = {...item, children: []};
current.push(treeNode);
trail.push(treeNode);
}
return tree;
}
const array = [
{id: 1, depth: 1, },
{id: 2, depth: 2, },
{id: 3, depth: 3, },
{id: 4, depth: 2, },
{id: 5, depth: 1, },
{id: 6, depth: 2, },
{id: 7, depth: 2, },
{id: 8, depth: 1, },
{id: 9, depth: 2, },
{id: 10, depth: 3 },
{id: 11, depth: 3 },
]
console.log(toTree(array));此解决方案克隆每个项目，以添加 .children 属性。如果不需要克隆，item 可以直接突变。
回答3
您可以获取最后插入的对象的数组。
const
data = [{ id: 1, depth: 1 }, { id: 2, depth: 2 }, { id: 3, depth: 3 }, { id: 4, depth: 2 }, { id: 5, depth: 1 }, { id: 6, depth: 2 }, { id: 7, depth: 2 }, { id: 8, depth: 1 }, { id: 9, depth: 2 }, { id: 10, depth: 3 }, { id: 11, depth: 3 }],
result = data.reduce((r, { depth, ...o }) => {
r[depth - 1].push({ ...o, children: r[depth] = [] });
return r;
}, [[]])[0];
console.log(result);.as-console-wrapper { max-height: 100% !important; top: 0; }