将具有级别信息的平面数组重新排列为具有子级的n元树

function buildTree(items) {
    const rootItems = [];
    const lookup = {};

    // 初始化lookup表
    items.forEach(item => {
        lookup[item.id] = { ...item, children: [] };
    });

    // 构建树结构
    items.forEach(item => {
        if (item.parentId === null || item.parentId === undefined) {
            rootItems.push(lookup[item.id]);
        } else {
            lookup[item.parentId].children.push(lookup[item.id]);
        }
    });

    return rootItems;
}

// 示例数据
const data = [
    { id: 1, name: 'Root', parentId: null },
    { id: 2, name: 'Child1', parentId: 1 },
    { id: 3, name: 'Child2', parentId: 1 },
    { id: 4, name: 'GrandChild1', parentId: 2 },
    { id: 5, name: 'GrandChild2', parentId: 2 }
];

console.log(JSON.stringify(buildTree(data), null, 2));

function hasCycle(node, lookup, path = []) {
    if (path.includes(node.id)) {
        return true;
    }
    path.push(node.id);
    for (const child of node.children) {
        if (hasCycle(child, lookup, path)) {
            return true;
        }
    }
    path.pop();
    return false;
}

function buildTreeSafe(items) {
    const rootItems = [];
    const lookup = {};

    items.forEach(item => {
        lookup[item.id] = { ...item, children: [] };
    });

    items.forEach(item => {
        if (item.parentId === null || item.parentId === undefined) {
            if (!hasCycle(lookup[item.id], lookup)) {
                rootItems.push(lookup[item.id]);
            }
        } else {
            if (!hasCycle(lookup[item.id], lookup)) {
                lookup[item.parentId].children.push(lookup[item.id]);
            }
        }
    });

    return rootItems;
}