TypeScript中的递归函数-父数组

Question

我想创建一个递归函数，接收包含id和parent_id的对象列表。如果元素的父元素在列表中，我想将其删除并添加到父元素中。

转换此：

{
"id": 180,
"children": [],
"parent_id": 195,
"name": "Object 180"
},
{
"id": 193,
"children": [],
"parent_id": 180,
"name": "Object 193"
},
{
"id": 194,
"children": [],
"parent_id": 180,
"name": "Object 194"
}
{
"id": 199,
"children": [],
"parent_id": 187,
"name": "Object 199"
}
{
"id": 304,
"children": [],
"parent_id": 193,
"name": "Object 304"
}

对此：

{
"id": 180,
"children": [
{
"id": 193,
"children": [
{
"id": 304,
"children": [],
"parent_id": 193,
"name": "Object 304"
}
],
"parent_id": 180,
"name": "Object 193"
},
{
"id": 194,
"children": [],
"parent_id": 180,
"name": "Object 194"
}
],
"parent_id": 195,
"name": "Object 180"
},
{
"id": 199,
"children": [],
"parent_id": 187,
"name": "Object 199"
}

有时parent_id为null，并且没有父级的级别限制。

Answer 1

因为basarat的答案不考虑嵌套在一个以上级别的项。

这里有一个创建具有任意嵌套深度的输出的解决方案：

const listToTree = (input) => {
const map = new Map(input.map((item) => [item.id, item]));

const output = [];
for (const item of input) {
if (map.has(item.parent_id)) {
map.get(item.parent_id).children.push(map.get(item.id));
} else {
output.push(map.get(item.id));
}
}
return output;
};
const input = [
{
"id": 180,
"value": 10,
"children": [],
"parent_id": 195,
"name": "Object 180"
},
{
"id": 193,
"value": 10,
"children": [],
"parent_id": 180,
"name": "Object 193"
},
{
"id": 194,
"value": 10,
"children": [],
"parent_id": 180,
"name": "Object 194"
},
{
"id": 199,
"children": [],
"parent_id": 187,
"name": "Object 199"
},
{
"id": 304,
"value": 10,
"children": [],
"parent_id": 193,
"name": "Object 304"
},
{
"id": 305,
"value": 10,
"children": [],
"parent_id": 194,
"name": "Object 304"
}
];
const output = listToTree(input);
console.log(output);

编辑：聚合值

如果您想沿着结果树的祖先链聚合值，我建议稍后在单独的函数中执行此操作。这将使您的代码更加干净、易于测试和可读。

实现取决于输入数组是否排序(子数组在父数组之前(。如果你想处理无序的输入，你必须循环通过每个祖先链。

function aggregateValue(branch) {
const children = branch.children || [];
return children.reduce((sum, child) => sum + aggregateValue(child), branch.value || 0);
}
function aggregateValueAlongBranches(tree) {
return tree.map((branch) => {
return {
...branch,
aggregatedValue: aggregateValue(branch),
children: aggregateValueAlongBranches(branch.children),
};
});
}
const input = [
{
"id": 180,
"value": 10,
"children": [
{
"id": 193,
"value": 10,
"children": [
{
"id": 304,
"value": 10,
"children": [],
"parent_id": 193,
"name": "Object 304"
}
],
"parent_id": 180,
"name": "Object 193"
},
{
"id": 194,
"value": 10,
"children": [
{
"id": 305,
"value": 10,
"children": [],
"parent_id": 194,
"name": "Object 304"
}
],
"parent_id": 180,
"name": "Object 194"
}
],
"parent_id": 195,
"name": "Object 180"
},
{
"id": 199,
"children": [],
"parent_id": 187,
"name": "Object 199"
}
];
const output = aggregateValueAlongBranches(input);
console.log(output);

Answer 2

您不需要递归函数。只需跟踪您已经看到的项目，如果其中存在父节点，则添加到parent.children或添加新的根节点。

附完整的解决方案示例。

完整代码

type Item = {
id: number,
children: Item[],
parent_id: number,
name: string,
}
const items: Item[] = [
{
"id": 180,
"children": [],
"parent_id": 195,
"name": "Object 180"
},
{
"id": 193,
"children": [],
"parent_id": 180,
"name": "Object 193"
},
{
"id": 194,
"children": [],
"parent_id": 180,
"name": "Object 194"
},
{
"id": 199,
"children": [],
"parent_id": 187,
"name": "Object 199"
},
{
"id": 304,
"children": [],
"parent_id": 193,
"name": "Object 304"
}
];

function nest(items:Item[]): Item[] {
const output: Item[] = [];
const idToItem = new Map<number,Item>();
for (let item of items) {
// Either add to parent. Or create a new root level node
if (idToItem.has(item.parent_id)) {
idToItem.get(item.parent_id)!.children.push(item);
} else {
idToItem.set(item.id, item);
output.push(item);
}
}
return output;
}
console.log(nest(items));