树形结构转列表

  1. /*
  2.     题目描述:
  3.         [
  4.             {
  5.                 id: 1,
  6.                 text: '节点1',
  7.                 parentId: 0,
  8.                 children: [
  9.                     {
  10.                         id:2,
  11.                         text: '节点1_1',
  12.                         parentId:1
  13.                     }
  14.                 ]
  15.             }
  16.         ]
  17.         转成
  18.         [
  19.             {
  20.                 id: 1,
  21.                 text: '节点1',
  22.                 parentId: 0 //这里用0表示为顶级节点
  23.             },
  24.             {
  25.                 id: 2,
  26.                 text: '节点1_1',
  27.                 parentId: 1 //通过这个字段来确定子父级
  28.             }
  29.             ...
  30.         ]
  31. */
  32. function tree2List(treeData) {
  33.     let result = []
  34.     const dfs = data => {
  35.         data.forEach(item => {
  36.             result.push(item)
  37.             if(item.children) {
  38.                 dfs(item.children)
  39.                 delete item.children
  40.             }
  41.         })
  42.     }
  43.     dfs(treeData)
  44.     return result
  45. }
  47. var treeData = [
  48.     {
  49.         id: 1,
  50.         text: '节点1',
  51.         parentId: 0,
  52.         children: [
  53.             {
  54.                 id:2,
  55.                 text: '节点1_1',
  56.                 parentId:1
  57.             }
  58.         ]
  59.     },
  60.     {
  61.         id: 2,
  62.         text: '节点2',
  63.         parentId: 0,
  64.         children: []
  65.     }
  66. ]
  67. tree2List(treeData)
  1. export function flattenDeep<T extends {children: T[];}>(list: T[], newList?: T[]): T[] {
  2.   if (!list.length) return list;
  4.   if (!newList) newList = [];
  5.   for (let index = 0; index < list.length; index++) {
  6.     const item = list[index];
  7.     // 拷贝 item ；目的：删除 copyItem 的 children 推送到 newList 中，最终返回的 newList 中就没有了 children 字段
  8.     const itemDeleteChild = JSON.parse(JSON.stringify(item));
  9.     if (Reflect.deleteProperty(itemDeleteChild, "children")) {
  10.       newList.push(itemDeleteChild);
  11.     }
  12.     if (item.children && !!item.children.length) {
  13.       flattenDeep(item.children, newList);
  14.     }
  15.   }
  16.   return newList;
  17. }
  1. type TMap = Map<
  2.   number,
  3.   {
  4.     parentId: number;
  5.     label: string;
  6.   }
  7. >;
  8. export function flattenDeepToMap<
  9.   T extends {
  10.     children: T[];
  11.   }
  12. >(list: T[], newList?: T[], tempMap?: TMap): TMap {
  13.   if (!list.length) return new Map();
  15.   if (!newList) newList = [];
  16.   if (!tempMap || !tempMap.size) tempMap = new Map();
  17.   for (let index = 0; index < list.length; index++) {
  18.     const item = list[index];
  19.     // 拷贝 item ；目的：删除 copyItem 的 children 推送到 newList 中，最终返回的 newList 中就没有了 children 字段
  20.     const itemDeleteChild = JSON.parse(JSON.stringify(item));
  21.     if (Reflect.deleteProperty(itemDeleteChild, "children")) {
  22.       tempMap.set(itemDeleteChild.id, {
  23.         parentId: itemDeleteChild.parentId,
  24.         label: itemDeleteChild.name,
  25.       });
  26.       newList.push(itemDeleteChild);
  27.     }
  28.     if (item.children && !!item.children.length) {
  29.       flattenDeepToMap(item.children, newList);
  30.     }
  31.   }
  32.   console.log(`tempMap---->`, tempMap);
  33.   return tempMap;
  34. }

列表转树形结构

  1. let arr = [
  2.   { id: 1, name: "部门1", parentId: 0 },
  3.   { id: 2, name: "部门2", parentId: 1 },
  4.   { id: 3, name: "部门3", parentId: 1 },
  5.   { id: 4, name: "部门4", parentId: 3 },
  6.   { id: 5, name: "部门5", parentId: 1 },
  7. ];
  9. /* 方法一：递归遍历查找（不推荐）时间复杂度为O(2^n) */
  10. function buildTree(list: any[], parentId: number, result: any[]) {
  11.   for (let item of list) {
  12.     if (item.parentId === parentId) {
  13.       const newItem = { ...item, children: [] };
  14.       result.push(newItem);
  15.       buildTree(list, item.id, newItem.children); // 重要，注意入参是：需要遍历的list ， 需要挂载的当前ID ， 需要挂载的当前 children
  16.     }
  17.   }
  18. }
  19. function FlattenToTree({ list, rootId }: { list: any[]; rootId: number }) {
  20.   const result: any[] = [];
  21.   buildTree(list, rootId, result);
  22.   return result;
  23. }
  24. // console.log(JSON.stringify(FlattenToTree({ list: arr, rootId: 0 })))
  1. /* 法二：不用递归，先把数据转成 Map 存储，之后遍历的同时借用 对象的引用，直接从 Map 中找到对应的数据做存储 */
  2. /* 两次循环，时间复杂度 O(2n)，需要 Map 把数据存储起来，空间复杂度 O(n) */
  3. /* 此方法会过滤掉当个无关联节点，只是将关联节点进行了构建。如：{id: 8, name: '部门4', parentId: 90} id/parentId 都与其他节点无关联 */
  4. function FlattenToTree_01({ list, rootId }: { list: any[]; rootId: number }) {
  5.   const result: any[] = [];
  6.   let tempMap: any = {}; // 作用：将所有可能出现的节点汇总，方便按层级进行挂载
  8.   for (const item of list) {
  9.     tempMap[item.id] = { ...item, children: [] };
  10.   }
  12.   for (const iterator of list) {
  13.     const id = iterator.id;
  14.     const parentId = iterator.parentId;
  16.     const treeItem = tempMap[id]; // 重要，当找到根节点时要 push 到 result 中
  18.     if (parentId === rootId) {
  19.       result.push(treeItem);
  20.     } else {
  21.       // 做这一步判断的目的是什么？？？
  22.       if (!tempMap[parentId]) {
  23.         tempMap[parentId] = {
  24.           children: [],
  25.         };
  26.       }
  27.       tempMap[parentId].children.push(treeItem);
  28.     }
  29.   }
  30.   return result;
  31. }
  32. // console.log(JSON.stringify(FlattenToTree_01({ list: arr, rootId: 0 })))
  1. /* 法三：不用递归。
  2.   思路：
  3.     数据转成 Map 存储，之后遍历的同时借助 对象的引用，直接从 Map 中找到对应的数据做存储。
  4.     与方法二不同点在于，遍历时即做 Map 存储，
  5. */
  6. function FlattenToTree_02({ list, rootId }: { list: any[]; rootId: number }) {
  7.   const result: any[] = [];
  8.   let tempMap: any = {}; // 作用：将所有可能出现的节点汇总，方便按层级进行挂载
  10.   for (const item of list) {
  11.     const id = item.id;
  12.     const parentId = item.parentId;
  14.     if (!tempMap[id]) {
  15.       tempMap[id] = {
  16.         children: [],
  17.       };
  18.     }
  20.     tempMap[id] = {
  21.       ...item,
  22.       children: tempMap[id]["children"],
  23.     };
  25.     const treeItem = tempMap[id];
  27.     if (parentId === rootId) {
  28.       result.push(treeItem);
  29.     } else {
  30.       if (!tempMap[parentId]) {
  31.         tempMap[parentId] = {
  32.           children: [],
  33.         };
  34.       }
  36.       tempMap[parentId].children.push(treeItem);
  37.     }
  38.   }
  39.   return result;
  40. }
  41. // console.log(JSON.stringify(FlattenToTree_02({ list: arr, rootId: 0 })))
  1. const otherParams = {
  2.   idName: "id",
  3.   parentName: "parentId",
  4.   childName: "children",
  5. };
  6. interface IGenerateTree {
  7.   list: any[];
  8.   rootId: number | string;
  9.   params?: typeof otherParams;
  10. }
  11. function generateTree({ list, rootId, params = otherParams }: IGenerateTree) {
  12.   const { idName, parentName, childName } = params;
  14.   const result: any[] = []; // 结果
  15.   let tempMap: any = {}; // 暂存数据，以 id 为 key 的映射关系
  17.   for (const item of list) {
  18.     const id = item[idName];
  19.     const parentId = item[parentName];
  21.     if (!tempMap[id]) {
  22.       tempMap[id] = {
  23.         [childName]: [],
  24.       };
  25.     }
  27.     tempMap[id] = {
  28.       ...item,
  29.       [childName]: tempMap[id][childName],
  30.     };
  32.     const treeItem = tempMap[id]; // 找到映射关系哪一项（注意这里是引用）
  34.     if (parentId === rootId) {
  35.       // 已经找到根元素，将映射结果放进结果集中
  36.       result.push(treeItem);
  37.     } else {
  38.       if (!tempMap[parentId]) {
  39.         tempMap[parentId][childName] = [];
  40.       }
  41.       tempMap[parentId][childName].push(treeItem);
  42.     }
  43.   }
  44.   return result;
  45. }
  46. console.log(JSON.stringify(generateTree({ list: arr, rootId: 0 })));