TypeScript中数组转树形结构的性能优化方案咨询

问题背景 #

现有Node类型的扁平数组，需转换为TreeNode类型的嵌套树形数组：

export interface Node {
  id: number;
  value: any;
  parent: number|null|undefined|false;
}

class TreeNode {
  private _id: Node['id'];
  private _value: Node['value'];
  private _parent: Node['parent'];
  private _children: TreeNode[] = [];

  constructor(node: Node, children: TreeNode[]) {
    this._id = node.id;
    this._value = node.value;
    this._parent = node.parent;
    this.children = children; // 自定义setter，非笔误
  }
}

原转换函数parseTree通过递归遍历数组匹配父节点，时间复杂度为O(n²)，数据量越大耗时越久：

// 预处理：将parent为null/undefined/false的节点统一设为-1（因id均为正数）
parseTree(array: Node[], id: Node['parent'] = -1): TreeNode[] {
  let tree: TreeNode[] = [];
  array.forEach((item, index) => {
    if (item.parent !== id) return;
    tree.push(new TreeNode(item, this.parseTree(array, item.id)));
  });
  return tree;
};

尝试用array.splice(index, 1)移除已处理元素优化时程序崩溃，需解决性能问题并修复崩溃原因。

崩溃原因分析 #

使用splice修改遍历中的数组会导致索引错乱：

• forEach遍历依赖数组原始长度和索引，splice移除元素后，后续元素前移，会跳过部分未处理元素
• 递归调用中操作同一个数组，会导致元素被重复移除或找不到目标节点，引发异常

优化方案：哈希映射法（时间复杂度O(n)） #

通过两次遍历+哈希表建立映射，避免重复遍历数组：

实现思路 #

1. 预处理节点：统一将parent为null/undefined/false的节点设为-1
2. 建立两个映射：
   • nodeMap：节点id到原Node对象的映射
   • parentChildrenMap：父节点id到对应子节点列表的映射
3. 递归/迭代生成树形结构，通过映射直接获取子节点，无需重复遍历数组

代码实现 #

parseTree(array: Node[], rootParentId: Node['parent'] = -1): TreeNode[] {
  // 1. 预处理parent字段（若未提前处理）
  const processedNodes = array.map(node => ({
    ...node,
    parent: node.parent == null || node.parent === false ? -1 : node.parent
  }));

  // 2. 构建映射表
  const nodeMap = new Map<number, Node>();
  const parentChildrenMap = new Map<number, Node[]>();

  processedNodes.forEach(node => {
    nodeMap.set(node.id, node);
    // 初始化父节点的子列表
    if (!parentChildrenMap.has(node.parent)) {
      parentChildrenMap.set(node.parent, []);
    }
    parentChildrenMap.get(node.parent)!.push(node);
  });

  // 3. 递归生成TreeNode
  const buildTree = (parentId: number): TreeNode[] => {
    const childrenNodes = parentChildrenMap.get(parentId) || [];
    return childrenNodes.map(node => new TreeNode(node, buildTree(node.id)));
  };

  return buildTree(rootParentId);
}

可选：迭代实现（避免递归栈溢出） #

若数据量极大，递归可能引发栈溢出，可改用迭代方式：

parseTree(array: Node[], rootParentId: Node['parent'] = -1): TreeNode[] {
  const processedNodes = array.map(node => ({
    ...node,
    parent: node.parent == null || node.parent === false ? -1 : node.parent
  }));

  // 先创建所有TreeNode实例，暂存映射
  const idToTreeNode = new Map<number, TreeNode>();
  const rootNodes: TreeNode[] = [];

  processedNodes.forEach(node => {
    idToTreeNode.set(node.id, new TreeNode(node, []));
  });

  // 关联父子节点
  processedNodes.forEach(node => {
    const currentNode = idToTreeNode.get(node.id)!;
    if (node.parent === rootParentId) {
      rootNodes.push(currentNode);
    } else {
      const parentNode = idToTreeNode.get(node.parent);
      if (parentNode) {
        parentNode.children = [...parentNode.children, currentNode];
        // 若TreeNode有addChild方法，可改用parentNode.addChild(currentNode)
      }
    }
  });

  return rootNodes;
}

优化效果 #

该方案仅需遍历数组2-3次，时间复杂度降至O(n)，大数据量下性能提升显著，同时避免了原方法中修改数组导致的崩溃问题。

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