给你一个数组，其中元素是节点值以及父节点值，要求去重并还原树｜网易前端面经解析

60 秒回答模板

我会先把输入约定清楚：每条记录有唯一 id、parentId 和节点值，parentId 为 null、undefined 或空字符串时视为根，0 是否为根要看题目约定。实现上第一遍遍历用 Map 按 id 去重并创建带 children 的节点，保留第一次出现的顺序；第二遍再按 parentId 找父节点，找到就 push 到父节点 children，根节点放 roots，父节点缺失放 orphans。重复 id 默认第一条决定父子关系，后续只补缺失的非结构字段；如果 parentId 冲突要记录冲突或直接报错。最后补环检测，避免 A 的父是 B、B 的父又是 A。这样时间复杂度 O(n)，空间复杂度 O(n)。

考点 核心机制与工程取舍

难度 中高频面试题

回答目标 按定义、机制、场景讲清楚

深入解析

输入约定和去重键

先把记录形态定成 { id, parentId, value }。id 是节点唯一键，parentId 是父节点 id。根节点只能用明确的空值判断，比如 null、undefined、空字符串；如果 parentId 可能是 0，不能用 if (!parentId) 判断根。

第一遍：Map 去重并建索引

遍历原数组时先查 Map。第一次遇到某个 id 就创建 { ...raw, children: [] } 并记录顺序；再次遇到同 id 时不创建新节点。默认策略是第一条决定 parentId，后续重复条只补齐缺失的非结构字段，parentId 冲突进入 conflicts 或抛错。

第二遍：按 parentId 挂载

第二遍只遍历去重后的节点顺序。parentId 是根值就放入 roots；parentId 能在 Map 中找到就 push 到父节点 children。因为第一遍已经收集完所有节点，所以父节点出现在子节点之后也不会丢。

多根和孤儿节点

多个根说明结果是森林，直接返回 roots 数组，或在展示层额外挂虚拟根。父节点不存在的节点不建议静默当根，否则脏数据会被伪装成合法根；更稳的是返回 orphans，让调用方决定报错、补数据还是单独展示。

循环引用检测

只要 parentId 关系里出现 self-loop 或祖先回指，就不是树。可以在挂载前对 id -> parentId 这张父指针图做 DFS 三色标记：访问中再次遇到同 id 说明有环，检测到环后直接报错或把环上节点放 invalidNodes。

顺序和复杂度

如果按第一次出现顺序保存去重节点，根节点顺序和兄弟节点顺序都能稳定复现原输入相对顺序。Map 查询让父节点查找从嵌套遍历的 O(n²) 降到均摊 O(1)，整体 O(n) 时间、O(n) 空间。

javascript

数组去重并还原树骨架

function buildTree(items) {
  const nodeMap = new Map();
  const order = [];
  const conflicts = [];

  const isRootParent = (parentId) =>
    parentId === null || parentId === undefined || parentId === "";

  for (const raw of items) {
    const { id, parentId } = raw;
    if (id === null || id === undefined || id === "") {
      throw new Error("node id is required");
    }

    if (!nodeMap.has(id)) {
      nodeMap.set(id, { ...raw, children: [] });
      order.push(id);
      continue;
    }

    const node = nodeMap.get(id);
    if (node.parentId !== parentId) {
      conflicts.push({ id, firstParentId: node.parentId, duplicateParentId: parentId });
    }
  }

  const roots = [];
  const orphans = [];

  for (const id of order) {
    const node = nodeMap.get(id);
    if (isRootParent(node.parentId)) {
      roots.push(node);
      continue;
    }

    const parent = nodeMap.get(node.parentId);
    if (parent) parent.children.push(node);
    else orphans.push(node);
  }

  return { roots, orphans, conflicts };
}

父节点可以后出现，因为第一遍已经把所有 id 放进 Map。
生产实现还要在挂载前做 parentId 环检测，避免递归渲染或序列化死循环。

易错点

单遍处理时子节点先于父节点出现，直接把子节点丢掉或误判成根。
每次挂载都用数组 find 找父节点，数据一大就退化成 O(n²)。
重复 id 创建多个节点实例，导致同一个业务节点出现在树的多个位置。
重复 id 的 parentId 冲突时静默用后者覆盖，树结构变得不可解释。
把 parentId 缺失和 parentId 指向不存在节点混为一谈，孤儿节点被错误挂成根。
用 if (!parentId) 判断根，导致 parentId 为 0 的合法父节点被误判为空。
不检测 A -> B -> A 这样的环，后续递归遍历、JSON 序列化或前端渲染可能无限递归。
复用输入对象并直接写 children，调用方再次传入同一批对象时 children 残留上一次构建结果。

面试官追问

如果父节点在子节点后面出现怎么办？

不要单遍边读边挂。第一遍先把所有去重节点放入 Map，第二遍再挂载，所以父节点出现顺序不影响查找。

重复 id 但 parentId 不一样怎么处理？

必须先定义策略。可以选择第一条决定结构，后续重复条不改 parentId，只补非结构字段；如果 parentId 冲突，就记录 conflicts 或直接抛错。

父节点不存在时是根节点吗？

不建议默认当根。题目说没有父节点是根，通常指 parentId 为空；parentId 指向不存在的 id 是孤儿节点，应进入 orphans 或报错。

多个根节点怎么返回？

返回 roots 数组，也就是森林。如果业务接口必须返回单棵树，可以额外创建虚拟根，但虚拟根是展示层包装，不应改变原始 parentId 语义。

如何检测循环引用？

把每个节点看成 id -> parentId 的父指针边，用 DFS 三色标记或当前路径集合检测。访问中再次遇到同一个 id，就是环，包括 parentId 等于自身的 self-loop。

如何保证兄弟节点顺序和复杂度？

第一遍记录每个 id 第一次出现顺序，第二遍按这个顺序 push 到父节点 children。每个节点和父指针最多处理常数次，所以时间 O(n)，额外 Map、children 和标记集合空间 O(n)。