JavaScript如何将depth深度数组转换为指定结构的嵌套对象

思路 #

用层级栈跟踪各深度最近的父节点，遍历深度数组时直接通过深度值定位父节点，不需要每次往前搜索，时间复杂度O(n)：

• 栈的下标对应节点的depth值，栈存储对应深度的最新节点引用
• 每生成一个新节点，直接加到depth-1对应栈节点的children数组里
• 把当前节点压入对应深度的栈位置，覆盖旧值，保证后续同深度或更深的节点能找到正确父级

可运行代码 #

const depth = [0, 1, 2, 3, 3, 2, 3, 3, 3];

function convertDepthToTree(depthArr) {
  // 栈：索引对应深度，值为对应深度的最新节点引用
  const stack = [];
  // 最终根节点数组
  const result = [];

  for (const type of depthArr) {
    const node = { type, children: [] };
    if (type === 0) {
      // 根节点直接加入结果
      result.push(node);
    } else {
      // 找父节点：深度为type-1的最新节点
      const parent = stack[type - 1];
      parent.children.push(node);
    }
    // 更新当前深度的栈节点为最新的当前节点
    stack[type] = node;
  }
  return { depth: result };
}

// 测试输出
console.log(JSON.stringify(convertDepthToTree(depth), null, 2));

输出结果 #

运行后和要求的目标结构完全匹配（原示例里第二个type字段多打了冒号的问题会自动修正）：

{
  "depth": [
    {
      "type": 0,
      "children": [
        {
          "type": 1,
          "children": [
            {
              "type": 2,
              "children": [
                { "type": 3, "children": [] },
                { "type": 3, "children": [] }
              ]
            },
            {
              "type": 2,
              "children": [
                { "type": 3, "children": [] },
                { "type": 3, "children": [] },
                { "type": 3, "children": [] }
              ]
            }
          ]
        }
      ]
    }
  ]
}

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