时间复杂度O(n)的数组转树结构算法
时间复杂度O(n)的数组转树结构算法
最近的工作单中遇到了这个问题,将接口给的数据结构转成树结构,于是就写了这个算法
测试数据
var flatArr = [ { id: 4, title: "节点4", parent_id: 3 }, { id: 5, title: "节点5", parent_id: 4 }, { id: 6, title: "节点6", parent_id: 2 }, { id: 1, title: "节点1", parent_id: 0 }, { id: 2, title: "节点2", parent_id: 0 }, { id: 3, title: "节点3", parent_id: 2 }, ];复制代码
完整代码
function Node(id, title) { this.id = id; this.title = title; this.leaf = true; this.children = []; } Node.prototype.addChild = function (node) { this.leaf = false; this.children.push(node); }; Node.prototype.setTitle = function (title) { this.title = title; }; var list = new Map(); flatArr.map(item => { var node = list.get(item.id); var parentNode = list.get(item.parent_id); if (node) { node.setTitle(item.title); } else { node = new Node(item.id, item.title); list.set(item.id, node); } if (parentNode) { parentNode.addChild(node); } else { let p = new Node(item.parent_id, "temp_node"); list.set(item.parent_id, p); p.addChild(node); } });复制代码
输出结果
console.log(JSON.stringify(list.get(0).children)); //[{"id":1,"title":"节点1","leaf":true,"children":[]},{"id":2,"title":"节点2","leaf":false,"children":[{"id":6,"title":"节点6","leaf":true,"children":[]},{"id":3,"title":"节点3","leaf":false,"children":[{"id":4,"title":"节点4","leaf":false,"children":[{"id":5,"title":"节点5","leaf":true,"children":[]}]}]}]}]
作者:jojowwbb
链接:https://juejin.cn/post/7018483751143342094