题目
对于前端来讲，经常需要自己构建组件，树就是其中一种，然而，对于树来讲，是存在一些不确定性的，比如树可能会很大， 一般后端会将树压扁了传给前端，当这个压扁了的数组很大的时候，前端可能就会面临一定的性能问题，你如何去解决？
分析
当时考官并没有刻意的为难自己，大概问了下自己做了哪些组件，我说了一些，随口说了句，比较简单的有树。
然后考官就揪着树问了上面的问题，同时还问我在应用中是怎么解决的。
我说，实际上也是将树拍扁了从后端传过来的，我印象里是用空间换时间的，因为做的时间太久远了，并不太记得，考官说可以实现一次遍历。
实践
不过，这还是一个比较经典也比较经常碰到的题目，所以我决定还是再次自己实践一下，毕竟自己的之前的实现可能存在各种问题。
数据定义
SingleTreeNode -- 压扁了的数据节点
export interface SingleTreeNode {
title: string; // 标题
parentId: string; // 父节点
id: string;
isLeaf: boolean; // 是否是叶子节点
weights: number; // 在同一个层级节点的权重，用来进行排序。可以是简单的index 0 1 2 3等
}
TreeNode -- 最终生成的树节点的数据格式
export interface TreeNode {
id?: string;
isLeaf?: boolean; // 是否是叶子节点
title?: string;
children?: Array<TreeNode>;
}
难点
总的来讲，其实并不算难这道题，难点主要是在于压扁了的节点之间可能是没有关系的，你遍历到了一个很深的节点，回过头来你可能会发现它的父亲、父亲的父亲可能都还不在。所以如何整理已经遍历的数据才是最重要的。
理解
用两个map进行存储，分别是
nodesmap、parentmap,其中，nodesmap用来存储遍历的数据，parentmap用来存储没有父节点的时候临时存放的数据。
之所以采用map是为了迅速的能够查询到对应的数据，而不是用耗时的数组的indexOf
代码(Typescript)
tree-order.ts
import { TreeNode, SingleTreeNode } from './tree-order';
export interface SingleTreeNode {
title: string; // 标题
parentId: string; // 父节点
id: string;
isLeaf: boolean; // 是否是叶子节点
weights: number; // 在同一个层级节点的权重，用来进行排序。可以是简单的index 0 1 2 3等
};
export interface TreeNode {
// level: number; // 树节点的层级 第一层是 1 第二层是2
id?: string;
isLeaf?: boolean; // 是否是叶子节点
title?: string;
children?: Array<TreeNode>;
[property:string]: any;
}
/**
*
* @param treeNodes 输入是一系列的压扁了的树节点，
* 要求： 以最优的方式去生成树。
*/
export function sortTree(singleTreeNodes: Array<SingleTreeNode>): Array<TreeNode>{
let res: Array<TreeNode> = [];
let nodesmap: Map<string,TreeNode> = new Map();
let parentmap: Map<string,Array<TreeNode>> = new Map();
let me = this;
// 考虑到 数组indexof的性能问题以及 对象只能以字符串作为键值的问题，这里可以考虑使用map来存放已经遍历过的数据。(当然直接用object也是可以的)
singleTreeNodes.forEach((singleTreeNode: SingleTreeNode,index: number)=>{
// $node: singleTreeNode data: [];
let treenode: TreeNode = sortTree.prototype.generateTreeNode(singleTreeNode);
nodesmap.set(singleTreeNode.id,treenode);
if(parentmap.has(singleTreeNode.id)) {
// 首先查看自己是否在父节点的map中
treenode.children = parentmap.get(singleTreeNode.id);
}
// 父节点的ID可能是空
if(singleTreeNode.parentId) {
if(nodesmap.has(singleTreeNode.parentId)) {
// 父节点已经存在过 添加到父节点中
let parentTreeNode: TreeNode = nodesmap.get(singleTreeNode.parentId);
// 添加到父节点中
sortTree.prototype.addSingleTreeNodeToParent(parentTreeNode.children,treenode);
} else {
// 父节点还不存在
if(!parentmap.get(singleTreeNode.parentId)) {
// 父节点的途中也不存在这个父节点
parentmap.set(singleTreeNode.parentId,[]);
}
let _arr = parentmap.get(singleTreeNode.parentId);
// 添加到临时的 parentmap中
_arr.push(treenode);
};
} else {
res.push(treenode);
}
})
return res;
};
sortTree.prototype.generateTreeNode = function(singleTreeNode: SingleTreeNode): TreeNode{
let obj: TreeNode = {
id: singleTreeNode.id,
title: singleTreeNode.title,
isLeaf: singleTreeNode.isLeaf
};
if(!singleTreeNode.isLeaf) obj.children = [];
return obj;
};
sortTree.prototype.addSingleTreeNodeToParent = function(data: Array<TreeNode>,node: TreeNode,newdata: boolean = false):Array<TreeNode>{
let me = this;
data.push(node); // 暂时不考虑权重，简单的插入
return newdata ? [...data] : data;
};
tree-order-test.ts
import { sortTree, SingleTreeNode } from './tree-order';
// let tree: Array<SingleTreeNode> = [
// {
// title: "1",
// }
// ]
function generateTree(arr?:Array<SingleTreeNode>,parentid?,deep?){
arr = arr || [];
parentid = parentid || '';
deep = deep || 1;
let maxdeep = 5;
let maxitem = 10;
let number = Math.ceil(Math.random() * maxitem); // 最大的数量
for(let i = 0; i < number;i++) {
let isLeaf:boolean = !!Math.round(Math.random()) || (deep == maxdeep);
let id = parentid + "" + i;
let obj = {
title: "" + Math.random() * 10,
weights: i,
parentId: parentid,
id: id,
isLeaf: isLeaf
};
arr.push(obj);
if(!isLeaf) {
generateTree(arr,id,deep + 1);
}
}
return arr;
};
let res = sortTree(generateTree());
console.log(JSON.stringify(res,null,4))
