>[success] # 把原始 list 转换成树形结构
~~~
1.以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门
编号，为 0 代表一级部门，现在要求实现一个 convert 方法，把原始 list 转换
成树形结构，parentId 为多少就挂载在该 id 的属性 children 数组下
~~~
~~~
// 原始 list 如下
let list =[
{id:1,name:'部门A',parentId:0},
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4}
];
const result = convert(list, ...);
// 转换后的结果如下
let result = [
{
id: 1,
name: '部门A',
parentId: 0,
children: [
{
id: 3,
name: '部门C',
parentId: 1,
children: [
{
id: 6,
name: '部门F',
parentId: 3
}, {
id: 16,
name: '部门L',
parentId: 3
}
]
},
{
id: 4,
name: '部门D',
parentId: 1,
children: [
{
id: 8,
name: '部门H',
parentId: 4
}
]
}
]
},
···
];
~~~
>[danger] ##### 用递归解决
~~~
let list = [
{ id: 4, name: "部门D", parentId: 1 },
{ id: 5, name: "部门E", parentId: 2 },
{ id: 6, name: "部门F", parentId: 3 },
{ id: 7, name: "部门G", parentId: 2 },
{ id: 1, name: "部门A", parentId: 0 },
{ id: 2, name: "部门B", parentId: 0 },
{ id: 3, name: "部门C", parentId: 1 },
{ id: 8, name: "部门H", parentId: 4 },
];
// 递归思路先找一个节点下的所有，即当前根节点为 0
// 就找到 第一个根节点中值为{ id: 1, name: "部门A", parentId: 0 }
// 开始递归找到 当前id:1 节点的子节点，即其他parentId 为1的节点
// 依次开始当找到 { id: 4, name: "部门D", parentId: 1 } 第一个
// parentId 为1的节点继续递归去找 parentId 4 的节点
function convert(source, parentId = 0) {
const ls = [];
for (let item of source) {
// 去找当前节点的子节点
if (parentId === item.parentId) {
// 这些去找它的子节点
const rs = convert(source, item.id);
// 把子节点拼接会现在节点
if (rs.length > 0) item.children = rs;
ls.push(item);
}
}
return ls;
}
console.log(convert(list));
~~~
>[danger] ##### 使用两个filter 过滤
~~~
let list = [
{ id: 4, name: "部门D", parentId: 1 },
{ id: 5, name: "部门E", parentId: 2 },
{ id: 6, name: "部门F", parentId: 3 },
{ id: 7, name: "部门G", parentId: 2 },
{ id: 1, name: "部门A", parentId: 0 },
{ id: 2, name: "部门B", parentId: 0 },
{ id: 3, name: "部门C", parentId: 1 },
{ id: 8, name: "部门H", parentId: 4 },
];
// 依次去找每个节点下的子节点
// 比如找到 id为2的子节点 可以写成 list.filter((item) => item.parentId === 2);
function convert(source, rootId = 0) {
return source.filter((rootNode) => {
const rs = source.filter((childrenNode) => {
return childrenNode.parentId === rootNode.id;
});
if (rs.length > 0) rootNode.children = rs;
return rootNode.parentId === rootId;
});
}
~~~
>[danger] ##### 利用map
~~~
let list = [
{ id: 4, name: "部门D", parentId: 1 },
{ id: 5, name: "部门E", parentId: 2 },
{ id: 6, name: "部门F", parentId: 3 },
{ id: 7, name: "部门G", parentId: 2 },
{ id: 1, name: "部门A", parentId: 0 },
{ id: 2, name: "部门B", parentId: 0 },
{ id: 3, name: "部门C", parentId: 1 },
{ id: 8, name: "部门H", parentId: 4 },
];
// 利用key value 形式
// 依次去循环找 到对应父节点，将当前节点插入回去父节点
function convert(source, rootId = 0) {
const map = list.reduce((res, v) => ((res[v.id] = v), res), {});
return source.filter((item) => {
if (item.parentId in map) {
const parentNode = map[item.parentId];
parentNode.children = parentNode.children || [];
parentNode.children.push(item);
}
return item.parentId === rootId;
});
}
console.log(convert(list));
~~~
>[info] ## 参考文章
[木易杨前端进阶](https://muyiy.cn/question/program/88.html)
- 接触数据结构和算法
- 数据结构与算法 -- 大O复杂度表示法
- 数据结构与算法 -- 时间复杂度分析
- 最好、最坏、平均、均摊时间复杂度
- 基础数据结构和算法
- 线性表和非线性表
- 结构 -- 数组
- JS -- 数组
- 结构 -- 栈
- JS -- 栈
- JS -- 栈有效圆括号
- JS -- 汉诺塔
- 结构 -- 队列
- JS -- 队列
- JS -- 双端队列
- JS -- 循环队列
- 结构 -- 链表
- JS -- 链表
- JS -- 双向链表
- JS -- 循环链表
- JS -- 有序链表
- 结构 -- JS 字典
- 结构 -- 散列表
- 结构 -- js 散列表
- 结构 -- js分离链表
- 结构 -- js开放寻址法
- 结构 -- 递归
- 结构 -- js递归经典问题
- 结构 -- 树
- 结构 -- js 二搜索树
- 结构 -- 红黑树
- 结构 -- 堆
- 结构 -- js 堆
- 结构 -- js 堆排序
- 结构 -- 排序
- js -- 冒泡排序
- js -- 选择排序
- js -- 插入排序
- js -- 归并排序
- js -- 快速排序
- js -- 计数排序
- js -- 桶排序
- js -- 基数排序
- 结构 -- 算法
- 搜索算法
- 二分搜索
- 内插搜索
- 随机算法
- 简单
- 第一题 两数之和
- 第七题 反转整数
- 第九题 回文数
- 第十三题 罗马数字转整数
- 常见一些需求
- 把原始 list 转换成树形结构