数组与树结构互转

扁平数组转树

function arrayToTree(items, rootParentId = null) {
  const nodeMap = new Map();
  const roots = [];

  for (const item of items) {
    nodeMap.set(item.id, { ...item, children: [] });
  }

  for (const item of items) {
    const node = nodeMap.get(item.id);

    if (item.parentId === rootParentId) {
      roots.push(node);
      continue;
    }

    const parent = nodeMap.get(item.parentId);
    if (parent) parent.children.push(node);
    else roots.push(node); // 也可以根据业务改为抛错
  }

  return roots;
}

两次线性遍历的时间复杂度是 O(n)、空间复杂度是 O(n)。不能对每个节点再用 find 寻找父节点，否则会退化为 O(n²)。

树转扁平数组

迭代写法可以避免极深树导致调用栈溢出：

function treeToArray(tree) {
  const result = [];
  const stack = [...tree].reverse();

  while (stack.length > 0) {
    const node = stack.pop();
    const { children = [], ...item } = node;
    result.push(item);

    for (let index = children.length - 1; index >= 0; index -= 1) {
      stack.push(children[index]);
    }
  }

  return result;
}

边界问题

面试中应主动确认：

  • ID 是否唯一，0 是否是合法 ID。
  • 根节点的 parentId 是 null、0 还是不存在。
  • 孤儿节点应该作为根、丢弃还是报错。
  • 数据是否可能存在环。
  • 是否需要保持输入顺序。

如果数据不可信，需要沿父链检测环，或在遍历时维护 visiting 与 visited 集合。发现环应报告数据错误，不能继续递归。