网站建设书本信息,it运维服务,做网站需要掌握什么,关于集团官方网站内容建设的报告注#xff1a;纯手打#xff0c;如有错误欢迎评论区交流#xff01; 转载请注明出处#xff1a;https://blog.csdn.net/testleaf/article/details/148628299 编写此文是为了更好地学习前端知识#xff0c;如果损害了有关人的利益#xff0c;请联系删除#xff01; 本文章… 注纯手打如有错误欢迎评论区交流 转载请注明出处https://blog.csdn.net/testleaf/article/details/148628299 编写此文是为了更好地学习前端知识如果损害了有关人的利益请联系删除 本文章将不定时更新敬请期待 欢迎点赞、收藏、转发、关注多谢 目录 【1】数组转树 【1】数组转树
数组转树是前端面试中的高频手写题通常用于处理扁平化的数据结构如菜单列表、评论嵌套等。 输入示例
const arr [{ id: 1, name: 部门A, parentId: 0 },{ id: 4, name: 部门D, parentId: 2 },{ id: 2, name: 部门B, parentId: 1 },{ id: 3, name: 部门C, parentId: 1 },
];输出示例
[{id: 1,name: 部门A,children: [{ id: 2, name: 部门B,children: [{ id: 4, name: 部门D, children: [] }]},{ id: 3, name: 部门C, children: [] }]}
]实现方法1【递归法O(n²)】
// 原始数据扁平化的部门列表每个部门有 id、name 和 parentId
const arr [{ id: 1, name: 部门A, parentId: 0 }, // 根节点parentId0{ id: 4, name: 部门D, parentId: 2 }, // 部门D 的父节点是部门Bid2{ id: 2, name: 部门B, parentId: 1 }, // 部门B 的父节点是部门Aid1{ id: 3, name: 部门C, parentId: 1 }, // 部门C 的父节点是部门Aid1
];
/*** 将扁平数组转换为树形结构* param {Array} items - 扁平数组* param {number} parentId - 当前层级的父节点ID默认0表示根节点* returns {Array} - 树形结构数组*/
const change (items, parentId 0) {let result []; // 当前层级的节点数组// 遍历所有部门找出属于当前 parentId 的子部门items.forEach(item {if (item.parentId parentId) {// 递归查找当前部门的子部门以当前部门的 id 作为父IDitem.children change(items, item.id);// 删除 parentId 字段可选树形结构不再需要该字段delete item.parentId;// 将当前部门添加到结果中result.push(item);}});return result; // 返回当前层级的部门树
};
// 打印完整的树形结构{depth:null} 表示展开所有层级
console.dir(change(arr), { depth: null });实现方法2【哈希表 一次遍历O(n)】
// 原始数据扁平化的部门列表每个部门有 id、name 和 parentId
const arr [{ id: 1, name: 部门A, parentId: 0 }, // 根节点parentId0{ id: 4, name: 部门D, parentId: 2 }, // 部门D 的父节点是部门Bid2{ id: 2, name: 部门B, parentId: 1 }, // 部门B 的父节点是部门Aid1{ id: 3, name: 部门C, parentId: 1 }, // 部门C 的父节点是部门Aid1
];
/*** 使用哈希表将扁平数组转换为树形结构O(n) 时间复杂度* param {Array} items - 扁平数组* returns {Array} - 树形结构数组*/
const change (items) {// 1. 初始化哈希表存储所有节点的引用方便后续通过 id 快速查找const map {};// 2. 结果数组存储所有根节点parentId0 的节点const result [];// 第一次遍历将所有节点存入哈希表并初始化 children 数组for (const item of items) {map[item.id] {...item, // 浅拷贝原对象避免直接修改原数据children: [] // 初始化子节点数组};}// 第二次遍历构建树形结构for (const item of items) {// 获取当前节点在哈希表中的引用const node map[item.id];if (item.parentId 0) {// 如果是根节点parentId0直接加入结果数组delete node.parentId; // 可选删除冗余的 parentId 字段result.push(node);} else {// 如果不是根节点找到父节点并挂载到父节点的 children 中if (map[item.parentId]) {delete node.parentId; // 可选删除冗余的 parentId 字段map[item.parentId].children.push(node);}// 注如果父节点不存在数据错误这里会静默忽略实际业务中可以报警告}}return result;
};
// 打印完整的树形结构{depth:null} 表示展开所有嵌套层级
console.dir(change(arr), { depth: null });思考 为什么 map[item.parentId].children.push(node) 会影响所有相关节点
JavaScript 的对象是引用类型 map[item.id] {...item, children: []} 创建的是 浅拷贝只拷贝第一层属性。map 中存储的是对节点的引用node 和 map[item.id] 指向同一个对象。 children 数组的共享 当执行 map[item.parentId].children.push(node) 时 map[item.parentId] 是父节点的引用。node 是子节点的引用。父子节点通过引用关联修改会同步反映到所有引用该对象的地方。
