JavaScript中如何高效获取树结构指定节点的所有后代节点

问题背景 #

给定以下扁平结构的树节点数组：

[
  { id: "1" },
  { id: "2" },
  { id: "3" },
  { id: "2.1", parent_id: "2" },
  { id: "3.1", parent_id: "3" },
  { id: "3.2", parent_id: "3" },
  { id: "3.1.1", parent_id: "3.1" },
  { id: "3.1.1.1", parent_id: "3.1.1" },
  { id: "3.1.1.1.1", parent_id: "3.1.1.1" },
  { id: "bohemian rhapsody", parent_id: "3.2" }
]

需求是从任意指定id的节点出发，获取其所有后代节点（包括自身）。原实现通过递归遍历整个数组完成，但每次递归都要扫描全量数据，效率较低，需要性能最优的方案（不关心遍历顺序是广度优先还是深度优先）。

原实现代码：

let source = []; // 数据源
let getDescendants = (id, source) => {
    let result = [];
  
    for (let node of source) {
     if (node.id === id) {
        result.push(node);
     } else if (node.parent_id === id) {
        result.push(...getDescendants(node.id, source));
     }
    }
  
    return result;
};

原方案性能问题 #

原方案的时间复杂度为O(n²)：每次递归都要遍历整个数组，对于链式结构（如3.1 → 3.1.1 → 3.1.1.1 → ...），每个节点都需要扫描全量数组一次，数据量越大性能越差。

最优性能方案 #

核心思路是预处理构建映射表，将父节点与子节点的关系提前存储，后续查询时直接通过映射快速获取子节点，无需再遍历全量数组。

步骤1：构建映射表 #

一次性遍历数组，生成两个映射：

• nodeMap：键为节点id，值为节点本身，用于快速查找目标节点
• childrenMap：键为父节点id，值为子节点数组，用于快速获取某节点的所有子节点

const buildTreeMaps = (source) => {
  const nodeMap = new Map();
  const childrenMap = new Map();

  for (const node of source) {
    nodeMap.set(node.id, node);
    // 初始化父节点的子数组容器
    if (!childrenMap.has(node.parent_id)) {
      childrenMap.set(node.parent_id, []);
    }
    // 若节点有父id，将其加入对应父节点的子数组
    if (node.parent_id) {
      childrenMap.get(node.parent_id).push(node);
    }
  }

  return { nodeMap, childrenMap };
};

步骤2：高效获取后代节点 #

基于映射表，用迭代方式（避免深层递归栈溢出）遍历节点及其所有子节点：

const getDescendants = (targetId, { nodeMap, childrenMap }) => {
  const result = [];
  const queue = [];

  // 先加入目标节点本身
  const targetNode = nodeMap.get(targetId);
  if (targetNode) {
    queue.push(targetNode);
  }

  while (queue.length > 0) {
    const currentNode = queue.shift(); // 广度优先；换成pop()则为深度优先
    result.push(currentNode);
    // 获取当前节点的所有子节点，加入队列继续遍历
    const children = childrenMap.get(currentNode.id) || [];
    queue.push(...children);
  }

  return result;
};

使用示例 #

// 原始数据源
const source = [
  { id: "1" },
  { id: "2" },
  { id: "3" },
  { id: "2.1", parent_id: "2" },
  { id: "3.1", parent_id: "3" },
  { id: "3.2", parent_id: "3" },
  { id: "3.1.1", parent_id: "3.1" },
  { id: "3.1.1.1", parent_id: "3.1.1" },
  { id: "3.1.1.1.1", parent_id: "3.1.1.1" },
  { id: "bohemian rhapsody", parent_id: "3.2" }
];

// 构建映射表（只需执行一次）
const treeMaps = buildTreeMaps(source);

// 获取id为"3"的所有后代节点
const descendants = getDescendants("3", treeMaps);
console.log(descendants);

性能说明 #

• 预处理阶段：时间复杂度O(n)，仅需执行一次
• 查询阶段：时间复杂度O(k)，其中k是目标节点及其后代的总数量，远优于原方案的O(n²)
• 若需多次查询，该方案的性能优势会更加明显

验证结果 #

传入id="3"时，输出结果与预期一致（以下为广度优先顺序，改为深度优先只需将shift()换成pop()）：

[
  { id: "3" },
  { id: "3.1", parent_id: "3" },
  { id: "3.2", parent_id: "3" },
  { id: "3.1.1", parent_id: "3.1" },
  { id: "bohemian rhapsody", parent_id: "3.2" },
  { id: "3.1.1.1", parent_id: "3.1.1" },
  { id: "3.1.1.1.1", parent_id: "3.1.1.1" }
]

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