2025年｜Javascript将列表还原为树状结构

问题关键点

在需要存储树结构的情况下，一般由于使用的关系型数据库（如 MySQL），是以类似表格的扁平化方式存储数据。因此不会直接将树结构存储在数据库中，通常是通过邻接表、路径枚举、嵌套集或闭包表来存储。

扁平列表通常包含id和parentId字段，通过parentId建立层级关系。
使用递归或循环方法构建树结构。

其中，邻接表是最常用的方案之一，其存储模型如下：

id pid data
1 0 a
2 1 b
3 1 c

该模型代表了如下的树状结构：

1
2
3
4
5
6
7
8
9
{
  id: 1,
  pid: 0,
  data: 'a',
  children: [
    {id: 2, pid: 1, data: 'b'},
    {id: 3, pid: 1, data: 'c'},
  ]
}

大部分情况下，会交给应用程序来构造树结构。

典型题目

1
2
3
4
5
6
7
8
const list = [
  { pid: null, id: 1, data: "1" },
  { pid: 1, id: 2, data: "2-1" },
  { pid: 1, id: 3, data: "2-2" },
  { pid: 2, id: 4, data: "3-1" },
  { pid: 3, id: 5, data: "3-2" },
  { pid: 4, id: 6, data: "4-1" },
];

M1
递归解法：该方法简单易懂，从根节点出发，每一轮迭代找到 pid 为当前节点 id 的节点，作为当前节点的 children，递归进行。

1
2
3
4
5
6
7
8
9
10
11
12
function listToTree(list,pid=null,{idName="id", pidName = "pid", childName = "children"} = {}){
  return list.reduce((root, item) => {
    if(item[pidName] === pid){
      const children = listToTree(list, item[idName]);
      if(children.length){
        item[childName] = children;
      }
      return [...root,item];
    }
    return root
  },[])
}

时间复杂度分析：最坏的情况下，这棵树退化为链表，且倒序排列。每一轮迭代需要在最后面才找到目标节点。假设有n个元素，那么总迭代次数为 n+(n-1) + (n-2) + … + 1，时间复杂度为 O(n^2)。

M2
迭代法：利用对象在 js 中是引用类型的原理。第一轮遍历将所有的项，将项的 id 与项自身在字典中建立映射，为后面的立即访问做好准备。 由于操作的每一项都是对象，结果集 root 中的每一项和字典中相同 id 对应的项实际上指向的是同一块数据。后续的遍历中，直接对字典进行操作，操作同时会反应到 root 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function listToTree(list, rootId=null,{idNmae="id", pidName="pid",childName="children"}={}){
  const record = {}
  const root = []

  list.forEach((item) => {
    record[item[idName]] = item;
    item[childName] = [];
  });

  list.forEach((item) => {
    if(item[pidName] == rootId){
      root.push(item)
    } else {
      record[item[pidName]][childName].push(item)
    }
  })

  return root;
}

时间复杂度分析：经历了两轮迭代，假设有 n 个元素，那么总迭代次数为 n + n，时间复杂度为 O(n)。

M2(1)

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
function listToTree(list, rootId=null,{idName="id", pidName="pid", childName="children"} ={}){
  const record = {};
  const root = []

  list.forEach((item) => {
    const id = item[idName]
    const parentId = item[pidName];

    record[id] = !record[id] ? item : {...item, ...record[id]};
    const treeItem = record[id]
    if(parentId === rootId){
      root.push(treeItem)
    } else {
      if(!record[parentId]){
        record[parentId] = {}
      }
      if(!record[parentId][childName]){
        record[parentId][childName] = [];
      }

      record[parentId][childName].push(treeItem);
    }
  })
  return root;
}

/**{ "id": 1, "name": "节点1", "parentId": null },
  { "id": 2, "name": "节点2", "parentId": 1 },
  { "id": 3, "name": "节点3", "parentId": 1 },
  { "id": 4, "name": "节点4", "parentId": 2 },
  { "id": 5, "name": "节点5", "parentId": null },
  { "id": 6, "name": "节点6", "parentId": 5 }**/
function listToTree1(list){
  const map = {};
  const rooots = []

  list.forEach((item) => {
    map[item.id] = {...item, children: []};
  })

  list.forEach((item) => {
    if(item.parentId === null){
      roots.push(map[item.id])
    } else {
      const parent = map[item.parentId]
      if(parent){
        parent.children.push(map[item.id])
      }
    }
  })

  return roots;
}

function listToTreeOptimized(list, {idNmae="id", pidName="pid", childName="children"} = {}){
  const map = new Map();
  cosnt roots = [];

  list.forEach((item) => {
    map.set(item[idName], {...item, [childName] : []})
  })

  list.forEach((item) => {
    const node = map.get(item[idName])
    if(item[pidName] == null){
      roots.push(node)
    } else {
      const parent = map.get(item[pidName])
      if(parent){
        parent[childName].push(node)
      }
    }
  })
  return roots
}



   // 渲染树状结构的函数
        function renderTree(nodes, container, level = 0) {
            nodes.forEach(node => {
                const nodeElement = document.createElement('div');
                nodeElement.className = 'tree-node';
                
                const contentElement = document.createElement('div');
                contentElement.className = 'node-content';
                contentElement.textContent = `${node.name} (ID: ${node.id})`;
                
                nodeElement.appendChild(contentElement);
                container.appendChild(nodeElement);
                
                if (node.children && node.children.length > 0) {
                    renderTree(node.children, nodeElement, level + 1);
                }
            });
        }

时间复杂度分析：经历了一轮迭代，假设有 n 个元素，那么时间复杂度为 O(n)。

M2(2)
record 字典仅记录 id 与 children 的映射关系，代码更精简：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function listToTree(list, rootId=null, {idName="id",pidName="pid",childName="children"} = {}){
  const record = {};
  const root = [];

  list.forEach((item) => {
    const newItem = Object.assign({}, item);
    cosnt id = newItem[idName];
    const parentId = newItem[pidName];

    newItem[childName] = record[id] ? record[id] : (record[id]=[])

    if(parentId === rootId){
      root.push(newItem);
    }else {
      if(!record[parentId]){
        record[parentId] = []
      }
      record[parentId].push(newItem)
    }
  })
  return root
}
  • 时间复杂度分析：经历了一轮迭代，假设有 n 个元素，那么时间复杂度为 O(n)。
  • 递归法：在数据量增大的时候，性能会急剧下降。好处是可以在构建树的过程中，给节点添加层级信息。
  • 迭代法：速度快。但如果想要不影响源数据，需要在 record 中存储一份复制的数据，且无法在构建的过程中得知节点的层级信息，需要构建完后再次深度优先遍历获取。
  • 迭代法变体一：按需创建 children，可以避免空的 children 列表。
  • 小数据量 (<1000条)：使用您的递归实现，代码更简洁
  • 大数据量或性能敏感：使用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
34
35
36
37
38
39
40
41
42
43
// 通用的深拷贝函数
// m1 const clonedList = JSON.parse(JSON.stringify(list));

function deepClone(obj) {
  if (obj === null || typeof obj !== 'object') return obj;
  if (obj instanceof Date) return new Date(obj);
  if (obj instanceof Array) return obj.map(item => deepClone(item));
  
  const cloned = {};
  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      cloned[key] = deepClone(obj[key]);
    }
  }
  return cloned;
}

function listToTreeWithDeepClone(
  list,
  { idName = "id", pidName = "pid", childName = "children" } = {}
) {
  const clonedList = deepClone(list);
  const map = new Map();
  const roots = [];
  
  clonedList.forEach(item => {
    map.set(item[idName], { ...item, [childName]: [] });
  });
  
  clonedList.forEach(item => {
    const node = map.get(item[idName]);
    if (item[pidName] === null) {
      roots.push(node);
    } else {
      const parent = map.get(item[pidName]);
      if (parent) {
        parent[childName].push(node);
      }
    }
  });
  
  return roots;
}

参考资料：

  1. 剑指前端offer