JavaScript实现树形数组转带level层级标识的扁平数组

根据你是否持有原始树形结构，分两种场景给出时间复杂度O(n)的最优实现，均支持任意深度的树结构：

场景1：可直接拿到原始树形结构（优先选这个方案） #

用深度优先遍历（DFS）遍历树，遍历过程中直接生成level字段，输出的结果天然符合你要的排序规则，不需要额外排序操作，性能最高。

递归版（绝大多数场景适用，代码最简洁） #

function treeToFlatWithLevel(tree) {
  const result = [];

  function dfs(nodeList, parentLevel = '') {
    nodeList.forEach((node, index) => {
      // 序号从1开始，根节点直接用序号，子节点拼接父级level
      const currentLevel = parentLevel 
        ? `${parentLevel}.${index + 1}` 
        : `${index + 1}`;
      // 剔除children字段，保留其余属性
      const { children, ...nodeProps } = node;
      result.push({ ...nodeProps, level: currentLevel });
      // 递归遍历子节点
      if (children?.length) dfs(children, currentLevel);
    });
  }

  dfs(tree);
  return result;
}

迭代版（适配极端超深树，无递归栈溢出风险） #

如果你的树深度超过JS默认递归栈上限（通常是1万层左右），可以用栈模拟递归，逻辑和递归版完全一致：

function treeToFlatWithLevelIter(tree) {
  const result = [];
  // 栈结构存储 [当前遍历的节点列表, 父级level]
  const stack = [[tree, '']];

  while (stack.length) {
    const [currentList, parentLevel] = stack.pop();
    // 倒序入栈保证出栈顺序和原数组顺序一致
    for (let i = currentList.length - 1; i >= 0; i--) {
      const node = currentList[i];
      const currentLevel = parentLevel
        ? `${parentLevel}.${i + 1}`
        : `${i + 1}`;
      const { children, ...nodeProps } = node;
      result.push({ ...nodeProps, level: currentLevel });
      if (children?.length) stack.push([children, currentLevel]);
    }
  }

  return result;
}

场景2：仅持有不带level的扁平数组 #

如果已经把树拍平成了无层级的数组，可以按以下步骤处理：

1. 构建id到节点的映射表，避免重复查找节点
2. 预处理每个父节点下的子节点顺序、根节点顺序
3. 加缓存回溯生成每个节点的level字段，避免重复计算
4. 将level拆为数字段排序，解决字符串排序下"1.10"排在"1.2"前的问题

function addLevelAndSort(flatList) {
  const idMap = new Map();
  const childOrderMap = new Map(); // 存每个父节点下的子节点id顺序
  const rootOrderMap = new Map(); // 存根节点的序号
  let rootIdx = 1;

  // 一次遍历预处理所有映射关系
  flatList.forEach(node => {
    idMap.set(node.id, node);
    if (node.parentId === null) {
      rootOrderMap.set(node.id, String(rootIdx++));
      return;
    }
    if (!childOrderMap.has(node.parentId)) childOrderMap.set(node.parentId, []);
    childOrderMap.get(node.parentId).push(node.id);
  });

  const levelCache = new Map(); // 缓存已计算的level，避免重复回溯
  function getLevel(node) {
    if (levelCache.has(node.id)) return levelCache.get(node.id);
    let level;
    if (node.parentId === null) {
      level = rootOrderMap.get(node.id);
    } else {
      const parentLevel = getLevel(idMap.get(node.parentId));
      const childIdx = childOrderMap.get(node.parentId).indexOf(node.id) + 1;
      level = `${parentLevel}.${childIdx}`;
    }
    levelCache.set(node.id, level);
    return level;
  }

  // 生成带level的数组
  const result = flatList.map(node => ({ ...node, level: getLevel(node) }));

  // 按level做自然排序
  result.sort((a, b) => {
    const segA = a.level.split('.').map(Number);
    const segB = b.level.split('.').map(Number);
    const minLen = Math.min(segA.length, segB.length);
    for (let i = 0; i < minLen; i++) {
      if (segA[i] !== segB[i]) return segA[i] - segB[i];
    }
    return segA.length - segB.length;
  });

  return result;
}

方案选型建议 #

• 只要能拿到原始树形结构，优先选场景1的DFS方案，代码更短、性能更好，不会出现排序逻辑错误
• 仅当拿不到原始树、只有扁平数组时，再用场景2的方案

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