如何根据对象type属性将平铺对象列表转换为多层嵌套层级结构

整体方案基于排序+哈希映射实现，时间复杂度O(n log n)，无递归逻辑，可稳定支持最多10级嵌套场景，不会出现路径误判、栈溢出问题。

核心实现步骤 #

• 预处理初始化
  首先创建硬编码值的根节点，给所有输入的平铺节点追加空children数组；之后把所有节点按type字段的字符串长度从小到大排序——父节点的type路径一定比子节点短，排序后处理任意节点时，它的所有潜在父节点都已经完成处理，不需要反向回溯查找。
• 建立快速查找映射
  用哈希表（Map）存储已经处理完成的节点，key为节点的type字段值，value为节点本身，把父节点查找的复杂度从O(n)降到O(1)。
• 迭代挂载节点
  按排序后的顺序遍历每个节点，从当前节点的type字符串末尾开始，按路径分隔符/逐段向上截断前缀，用截断后的前缀查哈希表：
  • 查到匹配节点时，直接把当前节点推入匹配节点的children数组，停止查找
  • 截断到没有分隔符还没找到匹配节点，说明当前节点是根节点的直接子节点，推入根节点的children数组
  • 为适配10级嵌套的要求，单节点向上查找父节点的截断次数最多设为9次（根为0级，10级子节点最多向上溯源9次），避免异常路径导致死循环
    节点挂载完成后，把当前节点存入哈希表，供后续更长路径的节点查找父节点使用。
• 边界兼容
  路径截断是按完整路径段操作，而非简单字符串前缀匹配，不会出现a/bc被错误识别为a/b子节点的问题；同type的重复节点会按输入顺序依次挂载，不会冲突。

可直接运行的JavaScript实现代码 #

function buildTypeTree(flatList) {
  // 初始化硬编码根节点
  const root = {
    name: "harcodedvalue",
    type: "harcodedvalue",
    children: []
  }
  const PATH_SEPARATOR = '/'
  const MAX_SUPPORT_LEVEL = 10

  // 预处理节点：追加空children，按type长度升序排序
  const sortedNodes = flatList.map(node => ({ ...node, children: [] }))
    .sort((prev, next) => prev.type.length - next.type.length)
  
  const typeMap = new Map()

  for (const currentNode of sortedNodes) {
    let parentPath = currentNode.type
    let targetParent = null

    // 最多向上查找9次，覆盖10级嵌套场景
    for (let i = 0; i < MAX_SUPPORT_LEVEL - 1; i++) {
      const lastSepPos = parentPath.lastIndexOf(PATH_SEPARATOR)
      if (lastSepPos === -1) break // 已经截到最顶层路径，停止查找
      parentPath = parentPath.slice(0, lastSepPos)
      if (typeMap.has(parentPath)) {
        targetParent = typeMap.get(parentPath)
        break
      }
    }

    // 挂载到对应父节点
    if (targetParent) {
      targetParent.children.push(currentNode)
    } else {
      root.children.push(currentNode)
    }

    // 存入映射供后续节点查找
    typeMap.set(currentNode.type, currentNode)
  }

  return root
}

// 测试用例
const flatTestData = [
  {"name": "test", "type": "sometype.type/test"},
  {"name": "test2", "type": "differenttype"},
  {"name": "test3", "type": "sometype.type/test/newtype"},
  {"name": "test4", "type": "sometype.type/test/newtype"}
]
console.log(buildTypeTree(flatTestData))

效率说明 #

• 排序步骤的时间复杂度为O(n log n)，单节点的父节点查找最多执行9次固定次数的字符串截断和哈希查询，整体处理效率接近线性，千级数据量下处理耗时在毫秒级。
• 全程采用迭代逻辑，没有递归调用，不存在栈溢出风险，10级嵌套的限制直接在查找次数上做了硬控制，稳定性更高。
• 路径匹配按完整路径段校验，不会出现部分前缀重合导致的父子关系误判，匹配精度符合业务要求。

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