FE-Interview
FE-Interview copied to clipboard
第 29 题:手写数组转树
欢迎在下方发表您的优质见解
let input = [
{
id: 1,
val: "学校",
parentId: null,
},
{
id: 2,
val: "班级1",
parentId: 1,
},
{
id: 3,
val: "班级2",
parentId: 1,
},
{
id: 4,
val: "学生1",
parentId: 2,
},
{
id: 5,
val: "学生2",
parentId: 3,
},
{
id: 6,
val: "学生3",
parentId: 3,
},
];
function buildTree(arr, parentId, childrenArray) {
arr.forEach((item) => {
if (item.parentId === parentId) {
item.children = [];
buildTree(arr, item.id, item.children);
childrenArray.push(item);
}
});
}
function arrayToTree(input, parentId) {
const array = [];
buildTree(input, parentId, array);
return array.length > 0 ? (array.length > 1 ? array : array[0]) : {};
}
const obj = arrayToTree(input, null);
console.log(obj);
例如
[{id:1, parentId: 0}, {id:2, parentId:1},{id:3, parentId:1}]
把这个数组从顶级分类递归查找子分类,最终构建一个树状数组。结果输出如下
[{id:1, parentId: 0,children:[{id:2, parentId:1},{id:3, parentId:1}]}]
parentId为0 的是根节点
代码实现
// 输入
const tempArr = [{
id: 1,
parentId: 0
},
{
id: 2,
parentId: 1
},
{
id: 3,
parentId: 1
},
{
id: 4,
parentId: 2
},
];
function arrayToTree(sourceArr) {
sourceArr.forEach(item => {
let parentId = item.parentId;
if (parentId !== 0) {
sourceArr.forEach(subitem => {
if (subitem.id == parentId) {
if (!subitem.children) {
subitem.children = [];
}
subitem.children.push(item);
}
});
}
});
return sourceArr.filter(item => item.parentId === 0);
}
console.log(arrayToTree(tempArr));
数组转树的其中一种,排序数组转二叉搜索树
/**
* function TreeNode(val) {
* this.val = val;
* this.left = null;
* this.right = null;
* }
*/
var sortedArrayToBST = function (nums) {
if (!nums.length) {
return null
};
const root = new TreeNode(null);
if (nums.length > 1) {
root.left = sortedArrayToBST(nums.splice(0, nums.length / 2))
};
root.val = nums[0];
root.right = sortedArrayToBST(nums.splice(1));
return root;
};
var list = [
{ id: 1, name: '部门A', 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 }
];
function convert(list) {
const map = list.reduce((acc, item) => {
acc[item.id] = item
return acc
}, {})
const result = []
for (const key in map) {
const item = map[key]
if (item.parentId === 0) {
result.push(item)
} else {
const parent = map[item.parentId]
if (parent) {
parent.children = parent.children || []
parent.children.push(item)
}
}
}
return result
}
var result = convert(list)
function convertStr(list) {
const res = [];
const map = new Map();
for (let i = 0; i < list.length; i++) {
map.set(list[i].id, list[i]);
}
for (let item of list) {
if (item.parentId == null) {
res.push(item);
} else {
const pItem = map.get(item.parentId);
pItem.children = pItem.children || [];
pItem.children.push(item);
}
}
return res;
}
function arrayToTree(array = []) {
// 获取祖先节点
const root = array.shift();
const tree = {
id: root.id,
val: root.val,
children: toTree(root.id, array)
};
return tree;
}
function toTree(parentId, array = []) {
const children = [];
for (let index = 0, len = array.length; index < len; index++) {
const node = array[index];
// 找到儿子节点
if (node.parentId === parentId) {
children.push({
id: node.id,
val: node.val,
children: toTree(node.id, array)
});
}
}
return children;
}
// 非递归版
const arrayToTree = (arr = []) => {
let map = {};
let tree = [];
for (let i in arr) {
map[arr[i].id] = arr[i];
}
for (let i in map) {
if (map[i].parentId) {
if (!map[map[i].parentId].children) {
map[map[i].parentId].children = [];
}
if (map[map[i].parentId].children) {
map[map[i].parentId].children.push(map[map[i].id]);
}
} else {
tree.push(map[i]);
}
}
return tree;
}
function arrToTre(params) { const result = params.map(item => { if (!item.children) { item.children = [] } const parent = findParent(item,params) parent && parent.children.push(item) return item }) return result[lowIndex(params)] } function findParent(obj,arr) { let result = null arr.map(item => { if (item.id === obj.parentId) { item.children ? '' : item.children = [] result = item } }) return result }
function lowIndex(arr) { let ind = Infinity let id = Infinity arr.map((item,index) => { if (item.id < id){ id = item.id ind=index } }) return ind } const result = arrToTre(input)
export const listToTree = (listData) => {
let ids = [],
objs = [];
listData.map(item => {
ids.push(item.id)
objs.push({
id:item.id,
title: item.label,
pid:item.pid,
children: []
})
})
let parents = []
objs.map( cur => {
let index = ids.indexOf(cur.pid)
if( index >=0 ){
objs[index].children.push(cur)
}else{
parents.push({
...cur,
isParent:true
})
}
} )
return parents
}
export function listToTree(soure, pid = 0) {
const result = []
let temp
soure.forEach((e) => {
if (e.parentId === pid) {
temp = listToTree(soure, e.id)
if (temp.length > 0) {
e.children = temp
}
result.push(e)
}
})
return result
}
let obj
for(let item of input){
if(!item.parentId) obj = item
const children = input.filter(it => it.parentId === item.id)
if(children.length > 0) item.children = children
}
var list = [ { id: 1, name: '部门A', 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 } ]; function convert(list) { const map = list.reduce((acc, item) => { acc[item.id] = item return acc }, {}) const result = [] for (const key in map) { const item = map[key] if (item.parentId === 0) { result.push(item) } else { const parent = map[item.parentId] if (parent) { parent.children = parent.children || [] parent.children.push(item) } else{ result.push(item) // 要加上else,否则,5,7就被抛弃了 } } } return result } var result = convert(list)
@523451928 要加上else,否则,5,7就被抛弃了
function transTree(arr) {
let map = arr.reduce((acc, item) => {
acc[item.id] = item;
item.children = [];
return acc
}, {})
for (const key in map) {
if (map.hasOwnProperty(key)) {
let node = map[key];
if (map[node.parentId]) {
map[node.parentId].children.push(node)
}
delete node.parentId;
}
}
return map[1];
}
console.log(transTree(input));
考的就是你对对象引用熟不熟
function arrToObj(arr) {
arr = Array.from(arr, (v, k) => Object.assign({}, v)); // 基于引用来的做的,这里的arr需要拷贝一下
let root = [];
arr.forEach(item => {
if(item.parentId == 0) {
root.push(item);
}else {
const parent = arr.find(iitem => iitem.id == item.parentId);
parent.children ? parent.children.push(item) : parent.children = [item];
}
});
return root;
}
const arr = [
{ id: 1, name: '部门A', parentId: 0 },
{ id: 3, name: '部门C', parentId: 1 },
{ id: 4, name: '部门D', parentId: 1 },
{ id: 5, name: '部门E', parentId: 0 },
{ id: 6, name: '部门F', parentId: 3 },
{ id: 7, name: '部门G', parentId: 0 },
{ id: 8, name: '部门H', parentId: 4 }
];
arrToObj(arr)
function setTreeData(data) {
let cloneData = JSON.parse(JSON.stringify(data)) // 对源数据深度克隆
let tree = cloneData.filter((father) => { //循环所有项
let branchArr = cloneData.filter((child) => {
return father.rankId == child.parentId //返回每一项的子级数组
});
if (branchArr.length > 0) {
father.children = branchArr; // 如果存在子级,则给父级添加一个children属性,并赋值
}
return father.parentId == 0; //返回第一层
});
return tree //返回树形数据
}
let data = [
{
rankId: 1,
value: 'BeiJing',
label: '北京',
parentId: 0,
},
{
rankId: 2,
value: 'jiangsu',
label: '江苏',
parentId: 0,
},
{
rankId: 3,
value: 'gugong',
label: '故宫',
parentId: 1,
},
{
rankId: 4,
value: 'tiantan',
label: '天坛',
parentId: 1,
},
{
rankId: 5,
value: 'zhengyangmen',
label: '正阳门',
parentId: 1,
}
]
console.log('setTreeData', setTreeData(data));
打印了一下各位大佬的代码,就想问一下,你们是怎么确定childnren一定是放在那个位置的?
时间复杂度 O(n) 的操作,不考虑原数组修改
function toTree(arr) {
var idMap = {}
arr.forEach((n) => {
idMap[n.id] = n
})
for (let i = 0; i < arr.length; i++) {
const node = arr[i]
const parentNode = idMap[node.parentId]
if (parentNode) {
if (Array.isArray(parentNode.children)) {
parentNode.children.push(node)
} else {
parentNode.children = [node]
}
}
}
return arr.filter((n) => n.parentId === 0)
}
我来提供一种方法,两次循环所以时间复杂度 O(n),使用 Object 临时存数据所以空间复杂度为 O(n),总体来说性能还是不错。
function array2Tree(arr) {
// key 为 id value 为 item
let obj = arr.reduce((acc, item) => {
acc[item.id] = item;
return acc;
}, {});
let root;
arr.forEach(item => {
if (item.parentId === null) {
root = item;
return;
}
let parentItem = obj[item.parentId];
if (!Array.isArray(parentItem.children)) {
parentItem.children = []
}
parentItem.children.push(item)
});
return root;
}
var test = array2Tree(input)
let input = [
{
id: 1,
val: "学校",
parentId: null,
},
{
id: 2,
val: "班级1",
parentId: 1,
},
{
id: 3,
val: "班级2",
parentId: 1,
},
{
id: 4,
val: "学生1",
parentId: 2,
},
{
id: 5,
val: "学生2",
parentId: 3,
},
{
id: 6,
val: "学生3",
parentId: 3,
},
{
id: 7,
val: "学校2",
parentId: null,
},
{
id: 8,
val: "班级1",
parentId: 7,
},
{
id: 9,
val: "班级2",
parentId: 7,
},
{
id: 10,
val: "学生1",
parentId: 8,
},
{
id: 11,
val: "学生2",
parentId: 9,
},
{
id: 12,
val: "学生3",
parentId: 8,
},
];
/**
*
* @param {Array} arr
*/
function listToTree(arr){
let tree = []
let temp = {}
arr.forEach((item) => {
item.children = []
temp[item.id] = item
if(!item.parentId){
tree.push(item)
}else{
temp[item.parentId].children.push(item)
}
})
return tree
}
console.log(listToTree(input))
/**
*
* @param {Array} tree
*/
function treeToList(tree){
let list = []
let temp = {}
function dfs(children){
for(let node of children){
if(!temp[node.id]){
list.push(node)
temp[node.id] = true
}
dfs(node.children)
delete node.children
}
}
dfs(tree)
return list
}
console.log(treeToList(JSON.parse(JSON.stringify(listToTree(input)))))
function toTree(data) {
var result = [];
var map = {};
data.forEach((item) => {
map[item.id] = item;
});
data.forEach((item) => {
var parent = map[item.parentId];
if (parent) {
(parent.children || (parent.children = [])).push(item);
} else {
result.push(item);
}
});
return result;
}
console.log(toTree(input))
function toTree(data) { var result = []; var map = {}; data.forEach((item) => { map[item.id] = item; }); data.forEach((item) => { var parent = map[item.parentId]; if (parent) { (parent.children || (parent.children = [])).push(item); } else { result.push(item); } }); return result; } console.log(toTree(input))
打印了一下各位大佬的代码,就想问一下,你们是怎么确定childnren一定是放在那个位置的?
@laihaoshan 先将数据转成树上的节点,然后根据 parentId
连边,parentId
为 null
的那个就是根节点。
function toTree(data) {
const idxMap = {}
const nodes = []
for (let i = 0; i < data.length; ++i) {
const { id, val } = data[i]
idxMap[id] = i
nodes.push({ val, children: [] })
}
let root
for (let i = 0; i < data.length; ++i) {
const p = data[i].parentId
if (p === null) root = nodes[i]
else nodes[idxMap[p]].children.push(nodes[i])
}
return root
}
type Node<T> = {
id: number;
value: T;
parentId: number;
};
type TreeNode<T> = {
id: number;
value: T;
parentId: number;
children: TreeNode<T>[];
};
const list: Node<string>[] = [
{ id: 1, value: 'V1', parentId: 0 },
{ id: 3, value: 'V2', parentId: 1 },
{ id: 4, value: 'V3', parentId: 1 },
{ id: 5, value: 'V4', parentId: 2 },
{ id: 6, value: 'V5', parentId: 3 },
{ id: 7, value: 'V6', parentId: 2 },
{ id: 8, value: 'V7', parentId: 4 },
];
const listToTree = <T>(list: Node<T>[]): TreeNode<T> | undefined => {
const map = list.reduce<Map<number, TreeNode<T>>>((prev, curr) => {
prev.set(curr.id, { ...curr, children: [] });
return prev;
}, new Map());
let headId = 1;
map.forEach((treeNode) => {
const parent = map.get(treeNode.parentId);
if (parent) {
parent.children.push(treeNode);
}
if(treeNode.parentId === 0) {
headId = treeNode.id;
}
});
return map.get(headId);
};
var list = [
{ id: 1, name: '部门A', 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 },
{ id: 18, name: '部门嗨', parentId: 4 },
];
function list2tree(list) {
let allIdList = list.map(item => item.id)
function attachChildrenPropIfNeeded(item, _) {
let children = list.filter(subItem => subItem.parentId === item.id).map(attachChildrenPropIfNeeded)
return {
...item,
...children?.length && { children }
}
}
return list.filter(item => !allIdList.includes(item.parentId)).map(attachChildrenPropIfNeeded)
}
console.log({ list, tree: list2tree(list) })
var arr = [{ id: 1, pid: '-1' }, { id: 11, pid: '1' }, { id: 12, pid: '1' }]
const flatArrayToTree = (arr) => {
let map = {};
let tree = new Array();
arr.map((value) => {
map[value.id] = value;
map[value.id].children = new Array();
});
arr.map((value) => {
if (value.pid !== '-1') map[value.pid].children.push(value);
else tree.push(value);
})
return tree;
}
console.log(flatArrayToTree(arr));
// 返回带有层级信息的树
const listToTreeWithLevel = function (list, parent, level) {
let output = [];
for (let node of list) {
if (node.pid === parent) {
node.level = level;
let children = listToTreeWithLevel(list, node.id, level + 1);
if (children.length) {
node.children = children;
}
output.push(node);
}
}
return output;
}
console.log(listToTreeWithLevel(arr, '-1', 0));
打印了一下各位大佬的代码,就想问一下,你们是怎么确定childnren一定是放在那个位置的?
因为js数组是引用的
//没看懂 还是写出来了
function Mtree(arr, pid = 0){
var tree = []
arr.forEach(item => {
if(item.pid == pid){
var children = Mtree(arr, item.id)
if(children.length > 0){
item.children = children
}
tree.push(item)
}
})
return tree
}
function toTree(arr) {
let [tree] = arr.map((item) => {
item.children = [];
item.children.push(
...arr.filter((child) => item.id === child.parentId)
);
return item;
}).filter(item => item.parentId === null);
return tree
}
/**
* 数组转树
* 一般指将一个扁平的数组转化为树状结构
* 其中每个对象已经具有独立id和指向父节点的parentId
* 转化为一个根节点数组,其中每个对象增加children属性
*/
function arrayToTree(arr) {
const rootNodes = [];
const idMap = {};
arr.map((node) => {
node.children = [];
idMap[node.id] = node;
});
arr.map((node) => {
const { parentId } = node;
if (parentId === null) {
rootNodes.push(node);
} else {
idMap[parentId].children.push(node);
}
});
return rootNodes;
}
const testArray = [
{
id: 1,
parentId: null,
data: 1,
},
{
id: 2,
parentId: 1,
data: 2,
},
{
id: 3,
parentId: 2,
data: 3,
},
{
id: 4,
parentId: null,
data: 4,
},
{
id: 5,
parentId: 1,
data: 5,
},
];
console.dir(JSON.stringify(arrayToTree(testArray)));
[
{
"id": 1,
"parentId": null,
"data": 1,
"children": [
{
"id": 2,
"parentId": 1,
"data": 2,
"children": [
{
"id": 3,
"parentId": 2,
"data": 3,
"children": []
}
]
},
{
"id": 5,
"parentId": 1,
"data": 5,
"children": []
}
]
},
{
"id": 4,
"parentId": null,
"data": 4,
"children": []
}
]