当前位置：首页 > news >正文

[面试] 手写题-数组转树

news 2025/6/30 7:22:44

示例数据：

const arr = [{ id: 1, parentId: null, name: 'Root' },{ id: 2, parentId: 1, name: 'Child 1' },{ id: 3, parentId: 1, name: 'Child 2' },{ id: 4, parentId: 2, name: 'Grandchild 1' },
]

目标生成：

const tree = [{id: 1,name: 'Root',children: [{id: 2,name: 'Child 1',children: [{ id: 4, name: 'Grandchild 1', children: [] }],},{id: 3,name: 'Child 2',children: [],},],},
]

递归

function arrayToTree(arr, pid) {let res = [];arr.forEach((item) => {// parentId 等于null即为根节点if (item.parentId === pid) {// 递归查找当前节点的所有子节点const children = arrayToTree(arr, item.id);item.children = children;res.push(item);}});return res;
}let result = arrayToTree(arr, null)
console.log(result);

时间复杂度较高O(n^2)

Map

时间复杂度O(n)

function arrayToTree(arr) {const map = new Map();// 使用Map，查找父节点时间复杂度为O(1)const res = []; // 返回根节点数组// 第一次遍历：将所有节点存入Map（id作为键，节点对象作为值）for (const item of arr) {map.set(item.id, item);// 注意：这里存储的是原始对象的引用}// 第二次遍历：构建树结构for (const item of arr) {if (item.parentId=== null) { // 根节点res.push(item);} else { // 有父节点，// 查找当前节点的父节点const parent = map.get(item.parentId);if (!parent.children) {parent.children = [];}// 将当前节点添加到父节点的children数组parent.children.push(item);}}return res; 
}

避免修改原始数据的一版本

// 此版本通过创建节点副本避免修改原始数据，
function arrayToTree(arr) {const map = new Map();const res = [];// 第一步：创建所有节点的副本（含children属性）for (const item of arr) {// 使用展开运算符{...item}创建浅拷贝，避免直接修改原始数据map.set(item.id, { ...item, children: [] });}// 第二步：构建树结构for (const item of arr) {// 从Map获取当前节点对应的副本，注意：这里使用副本节点而非原始数据const node = map.get(item.id); if (item.parentId === null) { // 根节点res.push(node);} else {// 获取父节点副本const parent = map.get(item.parentId);// 将当前节点添加到父节点的children数组parent.children.push(node); }}  return res;
}