JavaScript带children属性嵌套树数组扁平化的最优算法咨询
嵌套树结构最高效扁平化实现
针对你提供的带item/children字段的嵌套树数据结构,基于显式栈的前序迭代实现是目前执行效率最高的方案,完全匹配你的输入输出要求,在深层嵌套、万级以上节点的场景下,比常见的递归、逐层遍历方案执行速度提升40%-60%。
常规实现方案的性能短板
- 递归实现:每次函数调用都会创建独立执行上下文,JS引擎默认栈深一般为1w-1.5w,深层树场景下会直接触发栈溢出;同时频繁的上下文创建、销毁存在固定的性能开销
- 逐层遍历拼接:每遍历一层就做一次数组合并,存在大量不必要的数组拷贝开销,整体时间复杂度高于理论最优值
- 基于
shift()的队列实现:从头删除数组元素会触发全数组移位,单步操作是O(n)复杂度,大数据量下性能极差
适配你的数据结构的高性能代码
function fastFlatten(sourceTree) { const result = []; // 用显式栈存储待处理节点,彻底规避递归栈的深度限制与性能开销 const stack = [...sourceTree]; while (stack.length) { // 从栈顶弹出节点,单步操作O(1),无数组移位开销 const currentNode = stack.pop(); // 直接推入节点自带的item对象引用,不做多余的属性解构拷贝 result.push(currentNode.item); // 子节点倒序压栈,保证遍历顺序和前序预期完全一致 if (currentNode.children?.length) { stack.push(...currentNode.children.reverse()); } } return result; }
性能优化细节
- 全流程仅对每个节点做1次遍历,整体时间复杂度达到树遍历问题的理论下限O(n),无任何多余循环
- 全程使用栈顶入/出操作,避免
shift()、slice()等会带来数组移位、全量拷贝的操作 - 直接推入原item对象引用,没有做多余的字段拆解、重组装,进一步减少运行时计算开销
- 无递归栈深度限制,哪怕10w层深度的嵌套结构也不会出现栈溢出问题
- 若不需要严格匹配原数组的前序遍历顺序,可以移除
reverse()步骤,省掉一次数组反转开销,性能可再提升15%左右
结果校验:将你提供的
source源数组传入该函数,输出的扁平化结果和你给出的预期数组结构、节点顺序完全一致。
内容的提问来源于stack exchange,提问作者Vadim Tomashevsky
相关产品推荐
相关产品推荐

