先看一段数据结构

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
const list = [
  {
    id: 1,
    name: 'Node1',
    children: [
      {
        id: 3,
        name: 'Node1_1',
        children: [
          {
            id: 8,
            name: 'Node1_1_1'
          }, {
            id: 9,
            name: 'Node1_1_2'
          }, {
            id: 10,
            name: 'Node1_1_3'
          }]
      },
      {
        id: 4,
        name: 'Node1_2'
      },
      {
        id: 5,
        name: 'Node1_3'
      }]
  },
  {
    id: 2,
    name: 'Node2',
    children: [
      {
        id: 6,
        name: 'Node2_1'
      }, {
        id: 7,
        name: 'Node2_2'
      }]
  }
]

以上的数据结构是一个典型的树形结构，数组里面的每一项可能都会有 children 这个属性，然后 children 里面的每一项又是一个 list。

需求

通过传入任何一个 id 来找到所有的 parents 节点。
假如说我们传入的 id 是 8 那么它的 parentIds 就是[1, 3]

思路

  1. 定义一个空对象const map = {}
  2. 定义一个函数，传入循环的 list 和当前层级的 parentIds
  3. 循环这个 list 在每一项中map[item.id] = parentIds
  4. 假如该 item有 children 这个属性的话，就继续递归这个 children 然后把当前层级的 parents 和 prevParents 进行合并，用于下一次递归。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function findParentsById(list, id) {
  const map = {}; // 定义一个 map 对象
  function findParents(data, prevParents = []) {
    if (Array.isArray(data) && data.length) {
      // 遍历 data
      data.forEach(item => {
        // 每一次循环都创建一个 parents 使得每一层的 parents 都是独立的
        const parents = [];
        map[item.id] = prevParents;
        if (Array.isArray(item.children)) {
          parents.push(item.id)
          // 继续递归该 item.children, 把该层级新产生的 parents 和之前的 parents 进行合并，传给下一次递归调用
          findParents(item.children, [...prevParents, ...parents])
        }
      })
    }
  }
  findParents(list);
  // 最后生成的 map 对象里面包含了所有 id 的 parents
  return map[id];
}