数组转树

思路

• 遍历数组
• 每个元素，生成tree node
• 找到parentNode，并加入它的children

那如何找到 parentNode呢？

• 遍历数组查找太慢
• 可以用一个Map来维护关系，便于查找，时间复杂度O(1)

interface IArrayItem {
  id: number
  name: string
  parentId: number
}

interface ITreeNode {
  id: number
  name: string
  children?: ITreeNode[]
}

function convert(arr: IArrayItem[]): ITreeNode | null {
  // 用于id 和 treenode的映射
  const idToTreeNode: Map<number, ITreeNode> = new Map()
  let root = null
  arr.foreach(item => {
    const { id, name, parentId } = item
    // 定义tree node并加入map
    const treeNode: ITreeNode = { 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)
    }

    // 找到根节点
    if (parentId === 0) root = treeNode
  })
  return root
}