数组转为树

数组转化为树得常用方法总结

使用递归来遍历

提供一个genChildren方法，该方法递归去查找子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

 const arrayData = [
    {
        id: 3,
        title: '广东省',
        parent_id: 2
    },
    {
        id: 4,
        title: '广州市',
        parent_id: 3
    },{
        id: 2,
        title: '中国',
        parent_id: 0
    },
    {
        id: 5,
        title: '天河区',
        parent_id: 4
    },
    {
        id: 6,
        title: '湖南省',
        parent_id: 2
    },
    {
        id: 1,
        title: '俄罗斯',
        parent_id: 0
    }
]

function genChildren(data,result,rootId){
    for(let i = 0 ; i < data.length; i++){
        const item = data[i]
        if(item.parent_id === rootId){
            const newItem = {...item,children:[]}
            result.push(newItem)
            genChildren(data,newItem.children,item.id)
        }
    }
}

function arrayToTree(arr){
    const result = []
    genChildren(arr,result,0)
    return result
}

console.log(arrayToTree(arrayData))

时间复杂度 O(2^n)

不用递归，使用map来存储

先把数据转成Map去存储，之后遍历的同时借助对象的引用，直接从Map找对应的数据做存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function arrayToTree2(arr, rootId) {
  const arrMap = {}
  const result = []

  arr.forEach(item => {
      arrMap[item.id] = {...item,children:[]}
  })
  arr.forEach(item => {
      const id = item.id
      const pid = item.parent_id
      const newItem = arrMap[id]

      if(pid === rootId){
          result.push(newItem)
      }else{
          let parent = arrMap[pid].children
          parent.push(newItem)
      }
  })

  return result
}


console.log('arrayToTree2', arrayToTree2(arrayData, 0))

有两次循环，该实现的时间复杂度为O(2n)，需要一个Map把数据存储起来，空间复杂度O(n)

把两次遍历缩减为一次

主要思路也是先把数据转成Map去存储，之后遍历的同时借助对象的引用，直接从Map找对应的数据做存储。不同点在遍历的时候即做Map存储,有找对应关系。性能会更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function arrayToTree3(arr,rootId){
    const arrMap = {}
    const result = []

    arr.forEach(item => {
        const id = item.id
        const pid = item.parent_id

        if(!arrMap[id]){
            arrMap[id] = {children:[]}
        }

        arrMap[id] = {
            ...item,
            children:arrMap[id]['children']
        }
        
        const newItem = arrMap[id]

        if(pid === rootId){
            result.push(newItem)
        }else{
            if(!arrMap[pid]){
                arrMap[pid] = {children:[]}
            }
            arrMap[pid].children.push(newItem)
        }

    })
    return result
}

console.log('arrayToTree3', arrayToTree3(arrayData, 0))

一次循环就搞定了，该实现的时间复杂度为O(n)，需要一个Map把数据存储起来，空间复杂度O(n)