算法:通过数组构造树

题目
请把该数据整理为树状结构, 该树每个节点的结构如下,

   node = {
        children: [],
        id: id,
        value: value
    }

用例

var data = [{
            parentId: 0,
            id: 1,
            value: '1'
        }, {
            parentId: 3,
            id: 2,
            value: '2'
        }, {
            parentId: 0,
            id: 3,
            value: '3'
        }, {
            parentId: 1,
            id: 4,
            value: '4'
        }, {
            parentId: 1,
            id: 5,
            value: '5'
        }, ];

答案思路:
以map作为存储可以用户快速通过id获取节点,也可以使用字典存储
以parentId为父节点,遍历每个点,然后通过map拿到该parentId的节点,也就是拿到了父parent,
这时候只需要把子(当前节点)放进父里即可,遍历完成就放完了所有子节点。

注意
处理第一个父节点,判断拿到的parent为空则为他新建一个节点作为头结点,
第二次在拿到空的父节点,不能再建,要复用前面那个



        function fn(data) {
            const map = new Map()
            data.forEach(item => {
                map.set(item.id, item)
            })
            let root = null
            map.forEach((item, i) => {
                let parent = map.get(map.get(i).parentId) //拿到该节点的父节点
                if (!parent) {
                    if (!root) {
                        // 建根
                        parent = {
                            children: [],
                            id: map.get(i).parentId,
                            value: ''
                        }
                        root = parent
                    } else {
                        // 复用根
                        parent = root
                    }
                }
                parent.children = parent.children ? parent.children : []
                let son = map.get(i)
                delete(son.parentId)
                son.children ? son.children : son.children = []
                parent.children.push(son)
            })
            return root
        }
        console.log(fn(data))
上一篇:NOI 2020 D1T2 命运(Destiny) Solution


下一篇:JavaScript编程题