树形节点父优先排序及path属性生成的优化方案问询

给定节点数组：

const nodes = [
  { id: 1, parentId: 3 },
  { id: 2, parentId: 1 },
  { id: 3 },
  { id: 4, parentId: 3 },
  { id: 5, parentId: 2 },
  { id: 6, parentId: 1 },
  { id: 7, parentId: 4 },
  { id: 8, parentId: 7 },
  { id: 9, parentId: 8 },
];

需求：

• 排序数组，确保父节点始终出现在其子节点之前（子节点顺序无要求）
• 为每个节点添加path属性：根节点（无parentId）的path为自身id；子节点path由父节点path拼接当前id组成（示例用/分隔）

优化方案一：哈希表+迭代式遍历（高效无栈溢出） #

先通过哈希表预处理节点关系，再用栈实现迭代遍历，既保证父节点优先，又避免递归栈限制，整体时间复杂度O(n)。

function processNodes(nodes) {
  const nodeMap = new Map();
  const rootNodes = [];
  const childrenMap = new Map();

  // 初始化映射表
  for (const node of nodes) {
    nodeMap.set(node.id, node);
    if (!node.parentId) {
      rootNodes.push(node);
    } else {
      if (!childrenMap.has(node.parentId)) {
        childrenMap.set(node.parentId, []);
      }
      childrenMap.get(node.parentId).push(node);
    }
  }

  const result = [];
  const stack = [...rootNodes];

  while (stack.length > 0) {
    const current = stack.pop();
    // 设置path
    current.path = current.parentId ? `${nodeMap.get(current.parentId).path}/${current.id}` : `${current.id}`;
    result.push(current);
    // 子节点倒序入栈，保证原顺序（无需顺序可直接push）
    const children = childrenMap.get(current.id) || [];
    for (let i = children.length - 1; i >= 0; i--) {
      stack.push(children[i]);
    }
  }

  return result;
}

// 调用示例
const processed = processNodes(nodes);
console.log(processed);

优化方案二：尾递归实现（简洁且避免栈溢出） #

在严格模式下，V8等引擎支持尾递归优化，可将递归转为迭代执行，既保留递归的简洁性，又不会触发栈溢出。

'use strict';

function processNodesTailRecursive(nodes) {
  const nodeMap = new Map();
  const childrenMap = new Map();
  const rootNodes = [];

  // 初始化映射表
  for (const node of nodes) {
    nodeMap.set(node.id, node);
    if (!node.parentId) {
      rootNodes.push(node);
    } else {
      if (!childrenMap.has(node.parentId)) {
        childrenMap.set(node.parentId, []);
      }
      childrenMap.get(node.parentId).push(node);
    }
  }

  // 尾递归辅助函数
  function traverse(stack, result) {
    if (stack.length === 0) return result;

    const current = stack.pop();
    current.path = current.parentId ? `${nodeMap.get(current.parentId).path}/${current.id}` : `${current.id}`;
    result.push(current);

    const children = childrenMap.get(current.id) || [];
    for (let i = children.length - 1; i >= 0; i--) {
      stack.push(children[i]);
    }

    return traverse(stack, result);
  }

  return traverse([...rootNodes], []);
}

// 调用示例
const processedTail = processNodesTailRecursive(nodes);
console.log(processedTail);

方案优势 #

• 哈希表预处理后，父节点和子节点的查找都是O(1)操作，整体效率远高于无预处理的递归实现
• 迭代式版本完全规避递归栈限制，适合处理超大规模节点数组
• 尾递归版本在支持优化的引擎下，兼顾简洁性与性能

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