怎样在 O(n) 时间内把扁平列表转成树，再把树转回列表？

简答

对每个节点在列表里查找子节点是 O(n²)。先用 Map 按 id 建立索引，查找父节点变成 O(1)，总复杂度 O(n)。
先建全部节点再连接父子关系，子节点排在父节点前面也能正确挂载。
parentId 等于根标记，或者指向不存在的节点时，把节点放进根数组，避免孤儿节点丢失。
复制节点再添加 children，不修改调用方传入的数据。
树转列表用栈做前序遍历，入栈时带上父 id。用显式栈而不是递归，层级很深时不会栈溢出。

列表转树

JavaScript

function listToTree(list, { rootId = null } = {}) {
  const nodes = new Map();
  for (const item of list) nodes.set(item.id, { ...item, children: [] });

  const roots = [];
  for (const node of nodes.values()) {
    const parent = node.parentId === rootId ? undefined : nodes.get(node.parentId);
    // 根节点和父节点不存在的孤儿节点都放在第一层
    if (parent) parent.children.push(node);
    else roots.push(node);
  }
  return roots;
}

Map 按插入顺序遍历，同一父节点下的子节点保持它们在原列表中的顺序。id 重复时后出现的节点会覆盖前一个，需要在调用前校验数据。

树转列表

JavaScript

function treeToList(roots) {
  const result = [];
  // 反向入栈，保证出栈顺序与原来的兄弟顺序一致
  const stack = [...roots].reverse().map((node) => [node, null]);
  while (stack.length) {
    const [node, parentId] = stack.pop();
    const { children = [], ...rest } = node;
    result.push({ ...rest, parentId });
    for (let i = children.length - 1; i >= 0; i--) stack.push([children[i], node.id]);
  }
  return result;
}

每个节点入栈、出栈各一次，复杂度 O(n)。父 id 来自遍历时所在的位置，而不是节点上原有的 parentId，所以孤儿节点转回后 parentId 为 null。

验证

JavaScript

const list = [
  { id: 3, parentId: 1, name: 'c' },
  { id: 1, parentId: null, name: 'a' },
  { id: 2, parentId: 1, name: 'b' },
  { id: 4, parentId: 9, name: 'orphan' },
  { id: 5, parentId: 3, name: 'e' },
];

const tree = listToTree(list);
// a 的 children 为 [c, b]，c 的 children 为 [e]，orphan 是第二个根

console.log(treeToList(tree).map((n) => `${n.id}:${n.parentId}`).join(' '));
// 1:null 3:1 5:3 2:1 4:null

常见追问

数据里有环怎么办？例如 A 的父是 B、B 的父是 A，两者都不会出现在根数组里，转出的树会丢掉它们。需要在连接前检测，或在转换后检查节点总数是否一致。
如果要按 sort 字段排序？构建完成后对每个 children 排序，复杂度变为 O(n log n)。
树的遍历方式还有哪些？见《怎样用显式栈实现树的前序遍历？》。