题库/手写题/题目详解
手写题答案约 6 分钟阅读

列表转树与 DFS / BFS

先理解原理和示例，再练习完整口述与追问。

回答要点

先建索引再连接；检测重复、孤儿和环；避免 O(n²) 查找。

原理拆解

列表转树常先建 ID 到节点的映射，再按 parentId 建边，避免每个节点反复扫描全表。需要定义根、缺失父节点、重复 ID、自指和环的处理。DFS 适合沿路径深入，BFS 按层处理；两者访问节点可达一次时通常 O(n)，辅助空间取决于深度或最大层宽。

示例与推演

先用 A 为根、B/C 指向 A、D 指向 B 手算结果，再调换输入顺序，确认不依赖父在子之前。增加缺失父、自指与 A/B 成环，观察代码按契约报错或处理；DFS 深链可能栈溢出，BFS 用队列游标避免频繁 shift。

易错点

树算法不能默认输入永远是一棵合法树。遍历图时需要 visited，不应把重复引用和循环无限展开。

参考回答可直接练习口述

我用 Map 按 ID 建节点索引，先验证重复 ID 和父节点，再用线性标记检查父链是否成环，最后连接 children。下面约定 null/undefined 的 parentId 表示根，缺失父节点直接报错，不悄悄丢掉数据。保留输入顺序，每条节点创建新对象，children 字段由树结构统一生成。DFS 用栈，BFS 用队列指针，避免递归过深或反复 shift。

js
function listToForest(list) {
  if (!Array.isArray(list)) throw new TypeError('输入必须是数组')
  const nodes = new Map()
  for (const item of list) {
    const id = item && item.id
    const valid = typeof id === 'string' ||
      (typeof id === 'number' && Number.isFinite(id))
    if (!valid) throw new TypeError('id 必须是字符串或有限数字')
    if (nodes.has(id)) throw new Error('重复 id')
    nodes.set(id, { ...item, children: [] })
  }
  for (const node of nodes.values()) {
    if (node.parentId != null && !nodes.has(node.parentId)) {
      throw new Error('父节点不存在')
    }
  }
  const states = new Map()
  for (const node of nodes.values()) {
    const path = []
    let cursor = node
    while (cursor && states.get(cursor.id) !== 2) {
      if (states.get(cursor.id) === 1) throw new Error('父链存在环')
      states.set(cursor.id, 1)
      path.push(cursor.id)
      cursor = cursor.parentId == null ? null : nodes.get(cursor.parentId)
    }
    for (const id of path) states.set(id, 2)
  }
  const roots = []
  for (const node of nodes.values()) {
    if (node.parentId == null) roots.push(node)
    else nodes.get(node.parentId).children.push(node)
  }
  return roots
}

function dfsIds(roots) {
  const result = []
  const stack = [...roots].reverse()
  while (stack.length) {
    const node = stack.pop()
    result.push(node.id)
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i])
    }
  }
  return result
}

function bfsIds(roots) {
  const queue = [...roots]
  const result = []
  for (let index = 0; index < queue.length; index++) {
    const node = queue[index]
    result.push(node.id)
    for (const child of node.children) queue.push(child)
  }
  return result
}

示例：[{id:1,parentId:null},{id:2,parentId:1}] 得到根 1 下有子节点 2。重复、缺父、自环和互相指向均报错。建树和遍历平均 O(n)，空间 O(n)。这里节点其他嵌套业务字段仍是浅复制，遍历约定输入是无环森林，不能把任意图直接当树。