树形结构转数组

问题

将树形结构数据转换为扁平的数组列表。

// 输入
const tree = [
  {
    id: 1,
    name: '部门A',
    children: [
      { id: 2, name: '部门A-1', children: [] },
      { id: 3, name: '部门A-2', children: [
        { id: 4, name: '部门A-2-1', children: [] }
      ]}
    ]
  },
  {
    id: 5,
    name: '部门B',
    children: []
  }
]

// 输出
[
  { id: 1, name: '部门A', parentId: null },
  { id: 2, name: '部门A-1', parentId: 1 },
  { id: 3, name: '部门A-2', parentId: 1 },
  { id: 4, name: '部门A-2-1', parentId: 3 },
  { id: 5, name: '部门B', parentId: null }
]

解答

递归实现

function treeToArray(tree, parentId = null) {
  const result = []
  
  for (const node of tree) {
    // 提取当前节点，去掉 children 属性
    const { children, ...rest } = node
    
    // 添加 parentId 字段
    result.push({ ...rest, parentId })
    
    // 递归处理子节点
    if (children && children.length > 0) {
      result.push(...treeToArray(children, node.id))
    }
  }
  
  return result
}

// 使用
const list = treeToArray(tree)

迭代实现（广度优先）

function treeToArrayBFS(tree) {
  const result = []
  // 队列存储 [节点, 父节点ID]
  const queue = tree.map(node => [node, null])
  
  while (queue.length > 0) {
    const [node, parentId] = queue.shift()
    const { children, ...rest } = node
    
    result.push({ ...rest, parentId })
    
    // 子节点入队
    if (children && children.length > 0) {
      for (const child of children) {
        queue.push([child, node.id])
      }
    }
  }
  
  return result
}

迭代实现（深度优先）

function treeToArrayDFS(tree) {
  const result = []
  // 栈存储 [节点, 父节点ID]
  const stack = tree.map(node => [node, null]).reverse()
  
  while (stack.length > 0) {
    const [node, parentId] = stack.pop()
    const { children, ...rest } = node
    
    result.push({ ...rest, parentId })
    
    // 子节点入栈（逆序保证顺序正确）
    if (children && children.length > 0) {
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push([children[i], node.id])
      }
    }
  }
  
  return result
}

使用 reduce 实现

function treeToArrayReduce(tree, parentId = null) {
  return tree.reduce((acc, node) => {
    const { children, ...rest } = node
    
    // 添加当前节点
    acc.push({ ...rest, parentId })
    
    // 递归处理子节点并合并
    if (children && children.length > 0) {
      acc.push(...treeToArrayReduce(children, node.id))
    }
    
    return acc
  }, [])
}

关键点

• 使用解构 { children, ...rest } 分离子节点和其他属性
• 递归时传递当前节点 ID 作为子节点的 parentId
• 迭代实现需要用队列（BFS）或栈（DFS）存储待处理节点
• 栈实现时需要逆序入栈以保证遍历顺序
• 根节点的 parentId 为 null