第133题 把一个数组转换为树

    const arr = [
      {id:1, name: '部门A', parentId: 0},
      {id:2, name: '部门B', parentId: 1},
      {id:3, name: '部门C', parentId: 1},
      {id:4, name: '部门D', parentId: 2},
      {id:5, name: '部门E', parentId: 2},
      {id:6, name: '部门F', parentId: 3},
    ]

树节点

    interface ITreeNode {
      id:number
      name: string
      children?: ITreeNode[] // 子节点
    }

思路

• 遍历数组
• 每个元素生成TreeNode
• 找到parentNode，并加入它的children
  • 如何找到parentNode
    • 遍历数组去查找太慢
    • 可用一个Map来维护关系，便于查找

    /**
     * @description array to tree
     */
    
    // 数据结构
    interface ITreeNode {
      id: number
      name: string
      children?: ITreeNode[]
    }
    
    function arr2tree(arr) {
      // 用于 id 和 treeNode 的映射
      const idToTreeNode = new Map()
    
      let root = null // 返回一棵树 tree rootNode
    
      arr.forEach(item => {
        const { id, name, parentId } = item
    
        // 定义 tree node 并加入 map
        const treeNode = { id, name }
        idToTreeNode.set(id, treeNode)
    
        // 找到 parentNode 并加入到它的 children
        const parentNode = idToTreeNode.get(parentId)
        if (parentNode) {
          if (parentNode.children == null){
            parentNode.children = []
          }
          parentNode.children.push(treeNode) // 把treeNode加入到parentNode下
        }
    
        // 找到根节点
        if (parentId === 0) {
          root = treeNode
        }
      })
    
      return root
    }
    
    const arr = [
      { id: 1, name: '部门A', parentId: 0 }, // 0 代表顶级节点，无父节点
      { id: 2, name: '部门B', parentId: 1 },
      { id: 3, name: '部门C', parentId: 1 },
      { id: 4, name: '部门D', parentId: 2 },
      { id: 5, name: '部门E', parentId: 2 },
      { id: 6, name: '部门F', parentId: 3 },
    ]
    const tree = arr2tree(arr)
    console.info(tree)

连环问：把一个树转换为数组

• 思路
  • 遍历树节点（广度优先：一层层去遍历，结果是ABCDEF）而深度优先是（ABDECF）
  • 将树节点转为Array Item，push到数组中
  • 根据父子关系，找到Array Item的parentId
    • 如何找到parentId
      • 遍历树查找太慢
      • 可用一个Map来维护关系，便于查找

    /**
     * @description tree to arr
     */
    
    // 数据结构
    interface ITreeNode {
      id: number
      name: string
      children?: ITreeNode[]
    }
    
    function tree2arr(root) {
      // Map
      const nodeToParent = new Map() // 映射当前节点和父节点关系
    
      const arr = []
    
      // 广度优先遍历，queue
      const queue = []
      queue.unshift(root) // 根节点 入队
    
      while (queue.length > 0) {
        const curNode = queue.pop() // 出队
        if (curNode == null) break
    
        const { id, name, children = [] } = curNode
    
        // 创建数组 item 并 push
        const parentNode = nodeToParent.get(curNode)
        const parentId = parentNode?.id || 0
        const item = { id, name, parentId }
        arr.push(item)
    
        // 子节点入队
        children.forEach(child => {
          // 映射 parent
          nodeToParent.set(child, curNode)
          // 入队
          queue.unshift(child)
        })
      }
    
      return arr
    }
    
    const obj = {
      id: 1,
      name: '部门A',
      children: [
        {
          id: 2,
          name: '部门B',
          children: [
            { id: 4, name: '部门D' },
            { id: 5, name: '部门E' }
          ]
        },
        {
          id: 3,
          name: '部门C',
          children: [
            { id: 6, name: '部门F' }
          ]
        }
      ]
    }
    const arr = tree2arr(obj)
    console.info(arr)