请教一个树的构造算法问题

Question

/**
 * 这是全国所有的行政区域，大概4000个,value是该区域有多少用户，默认是0，后面会根据limit数组算
 */
let full= [
    {id: 1, pid: 0, label: '北京市', value: 0}, {id: 2, pid: 0, label: '福建省', value: 0}, {id: 3,pid: 0,label: '香港特别行政区',value: 0},
    {id: 4, pid: 1, label: '东城区', value: 0},
    {id: 5, pid: 2, label: '福州市', value: 0}, {id: 6, pid: 2, label: '厦门市', value: 0},
];

/**
 * 这是组装出来的全国行政区域的树
 */
let fullTree = [
    {id: 1, pid: 0, label: '北京市', value: 0, children: [{id: 4, pid: 1, label: '东城区', value: 0, children: []}]},
    {id: 2, pid: 0, label: '福建省', value: 0, children: [{id: 5, pid: 2, label: '福州市', value: 0, children: []}, {id: 6, pid: 2, label: '厦门市', value: 0, children: []}]},
    {id: 3, pid: 0, label: '香港特别行政区', value: 0,children:[]}
];

这是原始没有经过计算的树

/**
 * 这是所有用户的行政区域的并集，比如系统里就A和B两个用户，A是福建省，B是福建省厦门市，那么这里就是福建省和福建省厦门市
 */
let limit=[
    {id:6,pid:2,label:'厦门市',value:5}
];

/**
 * 这是根据limit和full数组算出来的树
 */
let limitTree=[
    {id:2,pid:0,label:'福建省',value:5,children:[{id:6,pid:2,label:'厦门市',value:5,children:[]}]}
];

这是计算后得到的树，想要达到这种效果

目前我是这么做的，遍历limit数组，从full数组里面一级一级往上找它的父节点并更新value，然后再把找到的这些节点组装成一棵树。
但是，如果limit数组一多，比如limit就是full数组，那么构造时间会好几秒，那就凉了。
我以前想过说就是full数组的value也查出来，组装好后再去自底向上裁剪掉value为0的节点，但是感觉还不如我现在的...
所以，有没有啥好的思路？

Answer 1

1.查询效率优化

把full数组重新排一下

let full= [
    {id: 1, pid: 0, label: '北京市', value: 0}, {id: 2, pid: 0, label: '福建省', value: 0}, {id: 3,pid: 0,label: '香港特别行政区',value: 0},
    {id: 4, pid: 1, label: '东城区', value: 0},
    {id: 5, pid: 2, label: '福州市', value: 0}, {id: 6, pid: 2, label: '厦门市', value: 0},
];
let full2 = [];
full.forEach(e => full2[e.id] = e)

查找父节点时直接通过full2[e.pid]获取。

2. 减少父节点赋值次数

树组装完成之前先不更新父节点的value,组装完成后通过一个递归去一次性更新

---

完整代码

let full= [
    {id: 1, pid: 0, label: '北京市', value: 0}, {id: 2, pid: 0, label: '福建省', value: 0}, {id: 3,pid: 0,label: '香港特别行政区',value: 0},
    {id: 4, pid: 1, label: '东城区', value: 0},
    {id: 5, pid: 2, label: '福州市', value: 0}, {id: 6, pid: 2, label: '厦门市', value: 0},
];


let limit=[
    {id:6,pid:2,label:'厦门市',value:5},
    {id: 2, pid: 0, label: '福建省', value: 6}
];

const t1 = new Date().getTime();

let full2 = [];
full.forEach(e => full2[e.id] = e);

const t2 = new Date().getTime();

const root = {id:0, pid:-1, label: 'root', value: 0};
full2[0] = root;

let limit2 = [];

limit.forEach(e => {
    const id = e.id;
    let v = Object.assign({}, full2[id]);
    v.value = e.value;
    limit2[id] = v;
});

let parents = [];
function assign2Parent(e) {
    const pid = e.pid;
    let parent = parents[pid];
    let children;
    if (parent) {
        children = parent.children;
        if (children.every(item => e.id !== item.id)){
            children.push(e);
        }
        return;
    }

    parent = limit2[pid];
    if (parent === undefined) {
        parent = full2[pid];
        if (!parent) {//不存在父节点
            return;
        }
        parent  = Object.assign({}, parent);
        parents[pid] = parent;
    }
    children = parent.children;
    if (!Array.isArray(children)) {
        parent.children = []
        children = parent.children;
    }
    if (children.every(item => e.id !== item.id)){
        children.push(e);
    }
    assign2Parent(parent);
}

limit2.forEach(e => assign2Parent(e));

function calcValues(node) {
    if (!node) {
        return 0;
    }
    const children = node.children;
    if (!children) {
        return node.value || 0;
    }
    const value = (node.value||0) +  children.reduce((v, e2) => v+calcValues(e2), 0);
    node.value = value;
    return value;
}

calcValues(parents[0]);

const t3 = new Date().getTime();
console.log('cost', t3-t1, t3-t2);
console.log(parents[0].children)

实测3500+数据可以在20毫秒内完成（cpu为i3-4170,内存8G DDR3 1600MHz）