JavaScript平铺数组转树形结构：递归与非递归性能对比

后台返回了1万条数据。

尽管有所预期，但后台确实一次性返回了上万条数据。虽然数量未达到10万条，但处理起来仍需谨慎。后台返回的数据结构如下所示：

const flatArr = [
  { id: '001', name: '节点1' },
  { id: '0011', parentId: '001', name: '节点1-1' },
  { id: '00111', parentId: '0011', name: '节点1-1-1' },
  { id: '002', name: '节点2' },
]

观察可知，这是一个平铺的数组结构。我们的需求是将此类数据渲染至Element-ui的级联选择器中，该组件要求接收如下格式的树形数据：

let options = [
  {
    value: 'zhinan',
    label: '指南',
    children: [
      {
        value: 'shejiyuanze',
        label: '设计原则',
        children: [
          { value: 'yizhi', label: '一致' },
          { value: 'fankui', label: '反馈'}
        ],
      }
    ]
  }
]

显然，这需要将平铺数组转换为树形结构。经过一番思考，决定采用递归方法实现。

递归方式

代码编写完成，逻辑简洁清晰。然而运行后发现页面卡死，通过console.time()统计，转换过程耗时约18秒。反思原因，面对上万条数据，递归方式在每次向下查找子节点时均需遍历整个数组，导致时间消耗巨大，直接引发页面卡顿，因此该方案不可取。是否存在更优方案？

非递归方式

此处巧妙利用了JavaScript中对象保存引用的特性。每次遍历时，以当前节点的id作为key，在对象映射表objMap中保存对应节点的引用。遍历过程中，持续更新objMap中各节点的children属性。最终，objMap中保留了所有节点及其子节点信息。关键在于，该方法仅需遍历数组一次，时间复杂度为O(n)。实际测试显示，计算耗时仅需60ms。

总结

• 递归方式：每次递归查找当前节点的子节点时，均需重新遍历数组，时间复杂度为O(nlogn)。
• 非递归方式：从根节点向下查找子节点，通过Map保存每个节点及其子节点信息。子节点保存的是Map中的引用，使得每个节点的子节点均可通过id在Map中快速定位，时间复杂度为O(n)。

对比结果如下：

从时间复杂度随数据量增长的趋势图可以看出，随着数据量增加，递归算法的耗时远超非递归算法。因此，在数据量较小时，递归算法具有一定优势；但当数据量达到一定规模时，递归算法的劣势愈发明显，此时使用非递归算法能显著提升速度。

通过上述对比，我们深刻体会到算法的重要性。不同的实现方式带来的性能差异巨大，这值得每一位开发者重视算法设计与优化。

本文关于JavaScript平铺数组转树形结构的实现示例介绍完毕。如需了解更多相关内容，请搜索本站往期文章或继续浏览后续文章，感谢支持。