百度云自助建站房产律师咨询免费24小时在线

注：纯手打，如有错误欢迎评论区交流！
转载请注明出处：https://blog.csdn.net/testleaf/article/details/148628299
编写此文是为了更好地学习前端知识，如果损害了有关人的利益，请联系删除！
本文章将不定时更新，敬请期待！！！
欢迎点赞、收藏、转发、关注，多谢！！！

【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 },  // 根节点（parentId=0）{ id: 4, name: '部门D', parentId: 2 },  // 部门D 的父节点是部门B（id=2）{ id: 2, name: '部门B', parentId: 1 },  // 部门B 的父节点是部门A（id=1）{ id: 3, name: '部门C', parentId: 1 },  // 部门C 的父节点是部门A（id=1）
];
/*** 将扁平数组转换为树形结构* @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 作为父ID）item.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 },  // 根节点（parentId=0）{ id: 4, name: '部门D', parentId: 2 },  // 部门D 的父节点是部门B（id=2）{ id: 2, name: '部门B', parentId: 1 },  // 部门B 的父节点是部门A（id=1）{ id: 3, name: '部门C', parentId: 1 },  // 部门C 的父节点是部门A（id=1）
];
/*** 使用哈希表将扁平数组转换为树形结构（O(n) 时间复杂度）* @param {Array} items - 扁平数组* @returns {Array} - 树形结构数组*/
const change = (items) => {// 1. 初始化哈希表：存储所有节点的引用，方便后续通过 id 快速查找const map = {};// 2. 结果数组：存储所有根节点（parentId=0 的节点）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) {// 如果是根节点（parentId=0），直接加入结果数组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 是子节点的引用。
    • 父子节点通过引用关联，修改会同步反映到所有引用该对象的地方。