完全忘了 itemMap[id]还代表了引用

[devwolf]

在看一个掘金的帖子 https://juejin.cn/post/6983904373508145189 “扁平数据结构转 Tree”。

看的时候在想，自己很少用 Map 对象，要不试试用 Map 改造一下，结果改造失败，找了半天原因，靠同事指了出来。

let arr = [
    { id: 1, name: "部门 1", pid: 0 },
    { id: 2, name: "部门 2", pid: 1 },
    { id: 3, name: "部门 3", pid: 1 },
    { id: 4, name: "部门 4", pid: 3 },
    { id: 5, name: "部门 5", pid: 4 },
];
let result = [];
function arrayToTree1(items) {
    const result = [];
    const itemMap = {};

    for (const item of items) {
        itemMap[item.id] = { ...item, children: [] };
    }

    for (const item of items) {
        const id = item.id;
        const pid = item.pid;
        const treeItem = itemMap[id];
        if (pid === 0) {
            result.push(treeItem);
        } else {
            if (!itemMap[pid]) {
                itemMap[pid] = {
                    children: [],
                };
            }
            itemMap[pid].children.push(treeItem);
        }
    }
    return result;
}
result = arrayToTree1(arr);
console.log(result);
console.log("========");

function arrayToTree2(items) {
    const result = [];
    const itemMap = new Map();
    items.map((item, index) => {
        itemMap.set(item.id, { ...item, children: [] });
    });
    items.map((item, index) => {
        const id = item.id;
        const pid = item.pid;
        const treeItem = itemMap.get(id);

        if (pid === 0) {
            result.push(treeItem);
        } else {
            if (!itemMap.get(pid)) {
                itemMap.set(pid, { children: [] });
            }

            itemMap.set(pid, {
                ...itemMap.get(pid),
                children: itemMap.get(pid).children.concat(treeItem),
            });
        }
    });
    return result;
}
result = arrayToTree2(arr);
console.log(result);

https://i.v2ex.co/1G1gNIox.png

中途甚至试着问了问 chat ，它没看出来啥区别敷衍了一下我 TAT 。后面我再想想能不能抢救一下 arrayToTree2

===接上一贴：裸辞了，但是单子还没提，总之大小领导都通知了。这里的规矩是通知完点头后才能提单子，这会儿学点自己想学的，边休息变沉淀一下了。

[shakukansp]

if (!itemMap.get(pid)) {
itemMap.set(pid, { children: [] });
}

const item = itermMap.get(pid)
item.children.push(treeItem)

[devwolf]

@shakukansp 感谢感谢，原来可以这样改，学到了

[shakukansp]

@devwolf arrayToTree1 改的是 itemMap[pid]的 chidren
你原本的写法 arrayToTree2 改的不是 itemMap.get(pid)的值的 children, 而是改了整个 itemMap.get(pid)的值

[TWorldIsNButThis]

啥意思
map 里存的是对 obj 的引用？

[shakukansp]

简单地说从柜子里面拿出来一个盒子，盒子里面放了另一个盒子，arrayToTree1 是在盒子(itemMap[pid])里面的盒子(children)里加了一个小盒子(treeitem)
arrayToTree2 是把最外面的大盒子(itemMap.get(pid))整个换掉了，所以你需要做的是不把最外面的盒子换掉，而是先拿出来，再往盒子里面的盒子加小盒子

[devwolf]

@TWorldIsNButThis 就是 #5 的那个巧妙的比喻。
itemMap[pid] 是个`大盒子`，itemMap[pid].children 是一个`中盒子`，treeitem 是`中盒子`里的`小盒子`。
需要的是更新`中盒子`里的内容，但是 arrayToTree2 中 itemMap.set 的做法改变了`大盒子`——这个角度上来讲，确实 不一样。
itemMap.set(pid, { ...itemMap.get(pid), children: itemMap.get(pid).children.concat(treeItem)}); 这段写成这样，
我初衷也是想在拷贝大盒子的同时只更新`中盒子`里的内容，虽然就结果而言并不如我所想的那样，这块我得慢慢悟一下为啥不一样，有成果了就回复你一下(手头来活还在忙别的)

[gitignore]

// normalize 对象，构建索引便于查找
const map = {};
for (const item of arr) {
item.children = [];
map[item.id] = item;
}
// 将对象添加至父节点
for (const item of arr) {
const parent = map[item.pid];
if (parent) {
parent.children.push(item);
}
}
// pid 为 0 就是根节点
return arr.filter(item => item.pid == 0);


=========
O(N) 复杂度。

是我不理解题意，还是考虑不周全，还是什么问题 😳

[devwolf]

😫完全不记得白天自己看这段代码的时候在想啥了。。。彷佛真在面试现场一样大脑浆糊翻滚,1 楼提醒了也没完全懂用意。
现在理了一下，确认我之前连 arrayToTree1 都没消化掉。
结合 shakukansp 的提示，我的理解是:
[题意] : id 区分每一个值,pid 标记位置,每个 id 按照 pid 来摆放。
[arrayToTree1] :
const treeItem = itemMap[id];//treeItem 保存了当前 id 的值

itemMap[pid].children.push(treeItem);//itemMap 虽然在创建时用 id 作为 key 但可以视作与 id 同值的 pid ，记录一个位置，以此来将 treeItem 放在合适的 children 里

[arrayToTree2] : 改造后
const _item = itermMap.get(pid);//这里就是正文里错误代码所欠缺的"盒子"
_item.children.push(treeItem);//在这个"盒子"里塞东西

------------
天亮我再想想

[devwolf]

一个上午的进展：
let a = {b:1}, c = a;
console.log(a);// { b: 1 }
c.b = 2;
a = {b:3};
console.log(a);// { b: 3 }
console.log(c);// { b: 2 }

let x = new Map(), z = x;
x['y'] = '方括号表示法 1';
x.set('y','set 赋值 1')
console.log(x.y);// 打印"方括号表示法 1"
console.log(x.get('y')) // 打印"set 赋值 1"

阶段总结：
原本以为是“换了一个写法”的"改引用的值还是改引用" 这类问题。
现在发现 Map 对象用 方括号 /点号表示法 存的位置和 set 不一样 🧐

[devwolf]

@gitignore 没啥问题啊，你这个对我而言可读性还更友好了。

@TWorldIsNButThis 不是这个意思，标题我是在未理解题意的时候起的，现在看来和标题关系不大了