如何在JavaScript中从扁平数组构建递归嵌套结构？

问题描述 #

现有一组扁平的JSON块数组，每个块的blocks字段可能包含子块ID或直接的文本对象。需要将所有ID替换为对应的完整块对象，形成递归嵌套的层级结构，最终只保留未被其他块引用的顶层块。

解决方案 #

核心思路是先建立块ID到块对象的映射表，再通过递归替换每个块的blocks字段中的ID，最后筛选出顶层块。

代码实现（JavaScript） #

function flattenToNested(flatBlocks) {
    // 构建ID与块对象的映射表，快速查找
    const blockMap = flatBlocks.reduce((map, block) => {
        map[block.id] = { ...block };
        return map;
    }, {});

    // 递归处理单个块的嵌套结构
    const processBlock = (block) => {
        block.blocks = block.blocks.map(item => {
            // 若为字符串ID，替换为对应块并递归处理其子块
            if (typeof item === 'string') {
                return processBlock(blockMap[item]);
            }
            // 直接文本对象无需处理，直接返回
            return item;
        });
        return block;
    };

    // 收集所有被引用的块ID，用于筛选顶层块
    const referencedIds = new Set();
    flatBlocks.forEach(block => {
        block.blocks.forEach(item => {
            if (typeof item === 'string') {
                referencedIds.add(item);
            }
        });
    });

    // 筛选未被任何块引用的顶层块，并处理嵌套
    return flatBlocks
        .filter(block => !referencedIds.has(block.id))
        .map(processBlock);
}

// 示例输入
const flatBlocks = [
    { "id": "1", "type": "p", "blocks": ["3","4","5"] },
    { "id": "2", "type": "h1", "blocks": ["6","7", "9"] },
    { "id": "3", "type": "p", "blocks": ["8"] },
    { "id": "4", "type":"p", "blocks": ["10"] },
    { "id": "5", "type":"p", "blocks": [{"text": "some text"}] },
    { "id": "6", "type":"p", "blocks": [{"text": "some more text"}] },
    { "id": "7", "type":"p", "blocks": [{"text": "some more text in id 7"}] },
    { "id": "8", "type":"p", "blocks": [{"text": "some more text in id 8"}] },
    { "id": "9", "type":"p", "blocks": [{"text": "some more text in id 9"}] },
    { "id": "10", "type":"p", "blocks": [{"text": "some more text in id 10"}] }
];

// 转换并输出结果
const nestedResult = flattenToNested(flatBlocks);
console.log(JSON.stringify(nestedResult, null, 2));

代码说明 #

1. 映射表构建：通过reduce将所有块存入以ID为键的对象，后续查找子块仅需O(1)时间。
2. 递归处理：processBlock函数遍历每个块的blocks字段，将ID替换为对应块，并递归处理子块的嵌套结构，确保所有层级都被正确转换。
3. 顶层块筛选：收集所有被引用的ID，筛选出未被引用的块作为顶层节点，避免重复输出子块。

运行上述代码后，将得到与需求一致的递归嵌套结构。

内容的提问来源于stack exchange，提问作者Rohan Keskar18