思路
- 遍歷數(shù)組
- 每個元素,生成tree node
- 找到parentNode,并加入它的children
那如何找到 parentNode呢浪感?
- 遍歷數(shù)組查找太慢
- 可以用一個Map來維護(hù)關(guān)系,便于查找,時間復(fù)雜度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)
}
// 找到根節(jié)點(diǎn)
if (parentId === 0) root = treeNode
})
return root
}