扁平数据与树结构互转

扁平数据与树结构互转

扁平数据常见于菜单、权限、评论、低代码 Schema 和接口响应。典型输入只有 id、parentId 和业务字段，目标是构造带 children 的树；反向转换则要恢复父子关系和稳定顺序。

1. 先确认数据契约

面试时先问清楚四件事：

1. 根节点的 parentId 是 null、undefined 还是某个固定值；
2. id 是否全局唯一，类型是否严格区分（1 和 '1' 是否相同）；
3. 孤儿节点、重复 ID、环和重复引用是报错、忽略还是挂到特殊根；
4. children 的顺序是否必须与输入顺序一致。

下面的实现采用严格契约：ID 必须唯一，非根节点的父节点必须存在，图必须是无环的，子节点顺序保留输入顺序。发现坏数据立即抛错，不静默丢节点。

2. 扁平列表转树

2.1 两遍法与不变量

第一遍只创建索引，保证父节点可能出现在子节点后面也能被找到；第二遍连接父子关系。循环过程中保持：

• nodes 包含输入中每一个 ID 的唯一节点副本；
• 处理到的节点要么已经挂到唯一父节点，要么已经进入 roots；
• children 只追加，不通过全树搜索定位父节点。

function listToTree(list) {
  if (!Array.isArray(list)) throw new TypeError('list must be an array')

  const nodes = new Map()
  const roots = []

  // 第一遍：建立 ID 索引，并避免修改输入对象。
  for (const item of list) {
    if (!item || item.id == null) {
      throw new TypeError('every item needs an id')
    }
    if (nodes.has(item.id)) {
      throw new Error(`duplicate id: ${String(item.id)}`)
    }
    nodes.set(item.id, { ...item, children: [] })
  }

  // 第二遍：按 parentId 连接节点。
  for (const node of nodes.values()) {
    if (node.parentId == null) {
      roots.push(node)
      continue
    }

    const parent = nodes.get(node.parentId)
    if (!parent) {
      throw new Error(
        `missing parent ${String(node.parentId)} for ${String(node.id)}`
      )
    }
    parent.children.push(node)
  }

  assertTree(nodes, roots)
  return roots
}

function assertTree(nodes, roots) {
  // 颜色标记：0/undefined=未访问，1=当前路径，2=已完成。
  const color = new Map()
  // 使用显式栈，避免不可信的深树耗尽 JavaScript 调用栈。
  for (const root of roots) {
    const rootState = color.get(root.id)
    if (rootState === 1) throw new Error(`cycle detected at ${String(root.id)}`)
    if (rootState === 2) throw new Error(`node referenced more than once: ${String(root.id)}`)

    color.set(root.id, 1)
    const stack = [{ node: root, nextChild: 0 }]
    while (stack.length) {
      const frame = stack[stack.length - 1]
      if (frame.nextChild >= frame.node.children.length) {
        color.set(frame.node.id, 2)
        stack.pop()
        continue
      }

      const child = frame.node.children[frame.nextChild]
      frame.nextChild += 1
      const state = color.get(child.id)
      if (state === 1) throw new Error(`cycle detected at ${String(child.id)}`)
      if (state === 2) throw new Error(`node referenced more than once: ${String(child.id)}`)
      color.set(child.id, 1)
      stack.push({ node: child, nextChild: 0 })
    }
  }
  if (color.size !== nodes.size) {
    // 有节点没有从任何根可达，通常意味着至少存在一个环或非法孤儿。
    throw new Error('unreachable node: input is not a rooted tree')
  }
}

两遍连接本身是 O(n) 时间和 O(n) 辅助空间。assertTree 也是 O(n)，上面使用显式栈避免递归深度限制。不要在循环中对 roots 反复做全树查找，否则最坏会退化到 O(n^2)。

2.2 ID 类型和输入顺序

Map 按 SameValueZero 判断键，因此数字 1 与字符串 '1' 是两个 ID。若后端把 ID 类型混用，应在建索引前统一规范化，而不是依赖隐式类型转换。Map 按插入顺序遍历，所以第二遍连接会保留列表中兄弟节点的相对顺序。

3. 树转扁平列表

递归 DFS 代码短，但深度来自外部数据时可能触发调用栈限制。显式栈可以在同样的先序顺序下工作，并用 seen 检测循环或共享节点：

function treeToList(roots) {
  if (!Array.isArray(roots)) throw new TypeError('roots must be an array')

  const result = []
  const seen = new Set()
  const seenIds = new Set()
  const stack = roots
    .slice()
    .reverse()
    .map((node) => ({ node, parentId: null }))

  while (stack.length) {
    const { node, parentId } = stack.pop()
    if (!node || node.id == null) throw new TypeError('invalid tree node')
    if (seen.has(node)) {
      throw new Error(`cycle or shared node at ${String(node.id)}`)
    }
    if (seenIds.has(node.id)) {
      throw new Error(`duplicate id in tree at ${String(node.id)}`)
    }
    seen.add(node)
    seenIds.add(node.id)

    const { children = [], ...record } = node
    if (!Array.isArray(children)) {
      throw new TypeError(`children must be an array at ${String(node.id)}`)
    }
    result.push({ ...record, parentId })

    // 反向压栈，出栈时仍是原 children 顺序。
    for (let index = children.length - 1; index >= 0; index -= 1) {
      stack.push({ node: children[index], parentId: node.id })
    }
  }

  return result
}

若只需要层序结果，可把同一个栈替换为带 head 索引的队列；不要频繁调用数组 shift()。输出空间（result）为 O(n)，显式栈最坏为 O(n)，平均可按树高说明。

4. 前序、中序、后序与层序

“前序/中序/后序”的区别只是访问根节点的时机：前序是 根 -> 左 -> 右，中序是 左 -> 根 -> 右，后序是 左 -> 右 -> 根。递归版本最接近定义；需要避免深度爆栈时，用显式栈保存尚未处理的节点。

function preorder(root) {
  const result = []
  const stack = root ? [root] : []
  while (stack.length) {
    const node = stack.pop()
    result.push(node.value)
    if (node.right) stack.push(node.right)
    if (node.left) stack.push(node.left)
  }
  return result
}

function inorder(root) {
  const result = []
  const stack = []
  let current = root
  while (current || stack.length) {
    while (current) {
      stack.push(current)
      current = current.left
    }
    current = stack.pop()
    result.push(current.value)
    current = current.right
  }
  return result
}

function postorder(root) {
  const result = []
  const stack = root ? [{ node: root, expanded: false }] : []
  while (stack.length) {
    const frame = stack.pop()
    if (frame.expanded) {
      result.push(frame.node.value)
      continue
    }
    stack.push({ node: frame.node, expanded: true })
    if (frame.node.right) stack.push({ node: frame.node.right, expanded: false })
    if (frame.node.left) stack.push({ node: frame.node.left, expanded: false })
  }
  return result
}

function levelOrder(root) {
  if (!root) return []
  const result = []
  const queue = [root]
  let head = 0
  while (head < queue.length) {
    const levelEnd = queue.length
    const level = []
    while (head < levelEnd) {
      const node = queue[head++]
      level.push(node.value)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    result.push(level)
  }
  return result
}

每个节点只访问一次，四种遍历的时间复杂度均为 O(n)。递归栈和 DFS 显式栈的额外空间为 O(h)（最坏退化树为 O(n)）；层序队列空间为最大层宽 O(w)（最坏也为 O(n)）。在 BST 中，中序结果有序；在普通二叉树中不能据此推断排序。

5. 追问与边界

Q: 为什么不能边遍历边找父节点？

A: 输入不保证父节点在前面。每次在当前树中搜索父节点会重复访问已有节点，最坏 O(n^2)；先建 Map 把定位降到均摊 O(1)，再做一次连接即可。（深入阅读：算法面试真题补充 - 扁平节点与树结构互转）

Q: JSON 转树和 JSON.parse 有什么区别？

A: 这里的“JSON”通常指扁平记录的数据形状，不是序列化协议。字符串仍需先 JSON.parse，树转字符串再 JSON.stringify；算法只负责记录之间的父子关系转换。

Q: 如何处理一个节点有多个父节点？

A: 那是 DAG 或脏数据，不再是树。若业务允许 DAG，应改用 parents/引用计数等图模型，并明确序列化去重策略；不能用树的 parentId 字段悄悄覆盖其中一个父节点。

Q: 为什么要校验环？

A: 环无法从根节点遍历完，递归会无限调用，迭代会不断重复入栈。颜色标记能在线性时间内区分“当前路径回边”和“重复引用”，生产接口还应限制最大节点数和最大深度。

6. 面试检查清单

• 空列表返回 []；只有根节点时 children 仍为空数组。
• 子节点先出现、多个根、缺失父节点、重复 ID、1 与 '1' 混用。
• 环 A -> B -> A、共享子节点和深度超过递归栈的输入。
• 是否复制节点、是否保留额外字段、是否保证兄弟顺序。
• 时间复杂度写 O(n)，并把索引、结果和递归/显式栈空间分别说明。

来源：高频真题解析与9月考点预测中.pdf 的“JSON 转树/树转 JSON”和“前序中序后序”题；与 前端高频算法原题解析.pdf 的树/复杂度分析方法结合整理。

相关专题：树遍历模板、广度优先搜索、复杂度分析方法。