BluePen BluePen
  • Jenkins
  • OS
  • 算法
随笔
分类
标签
归档
关于
留言板
GitHub (opens new window)

Alex

一个好人
  • Jenkins
  • OS
  • 算法
随笔
分类
标签
归档
关于
留言板
GitHub (opens new window)
  • leetcode

  • interview

    • 扁平树结构转换为嵌套json
      • 题目描述
      • 解法
      • 总结
    • 走格子
    • Dynamic Programming 示例
    • 猜数字游戏
    • 数组划分
  • well_known_algo

  • algo
  • interview
Alex
2019-07-08
目录

扁平树结构转换为嵌套json

-> 题目描述

数据库中存有扁平树结构如下:

id pid label depth
1 0 1 1
2 1 1-1 2
3 1 1-2 2
4 1 1-3 2
5 3 1-2-1 3
6 4 1-3-1 3
7 5 1-2-1-1 4
8 4 1-3-2 3
9 3 1-2-2 3
10 8 1-3-2-1 4

需要转转为如下数据结构

[
  {
    "id": 1,
    "pid": 0,
    "label": "1",
    "depth": 1,
    "children": [
      {"id": 2, "pid": 1, "label": "1-1", "depth": 2, "children": [] },
      {"id": 3, "pid": 1, "label": "1-2", "depth": 2,
        "children": [{
            "id": 5, "pid": 3, "label": "1-2-1", "depth": 3, 
            "children": [{
              "id": 7, "pid": 5, "label": "1-2-1-1", "depth": 4, "children": []
            }]
          },
          { "id": 9, "pid": 3, "label": "1-2-2", "depth": 3, "children": [] }
        ]
      },
      {"id": 4, "pid": 1, "label": "1-3", "depth": 2,
        "children": [
          {
            "id": 6, "pid": 4, "label": "1-3-1", "depth": 3, "children": []
          },
          {
            "id": 8, "pid": 4, "label": "1-3-2", "depth": 3, 
            "children": [{
              "id": 10, "pid": 8, "label": "1-3-2-1", "depth": 4, "children": []
            }]
          }
        ]
      }
    ]
  }
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

-> 解法

点击查看
/**
 * @param {[object]} list
 * @return {[object]}
 * 
 * */
const transListToJsonTree = function(list) {
    function Node(node) {
        this.id = node.id
        this.label = node.label
        this.depth = node.depth
        this.pid = node.pid

        this.left = null
        this.right = null
        this.parent = null
    }

    function BinaryTree() {
        this.root = null
        this.nodes = []
    }
    BinaryTree.prototype.insert = function(node) {
        let curr_node = node
        if (node instanceof Node === false) {
            curr_node = new Node(node)
        }
        if (!this.root && curr_node.depth === 1) {
            this.root = curr_node
            this.nodes.push(curr_node)
            return true
        } else {
            let root = this.nodes[0]
            while (true) {
                if (curr_node.depth > root.depth) {
                    if (curr_node.depth - root.depth !== 1) {
                        root = root.right || root.left //非相邻节点直接直接跨级
                    } else {
                        if (curr_node.pid === root.id) {
                            if (root.right === null) {
                                root.right = curr_node
                                curr_node.parent = root
                                this.nodes.push(curr_node)
                                return true
                            }
                            root = root.right
                        } else {
                            if (root.left) { //尝试遍历左节点的下级
                                root = root.left
                            } else { //如果不存在左节点说明走错了,返回上级节点左节点继续遍历
                                while (root.parent.id !== root.pid) {
                                    root = root.parent
                                }
                                root = root.parent.left
                            }
                        }
                    }
                } else if (curr_node.depth === root.depth) { //同级节点放在最左
                    if (root.left === null) {
                        root.left = curr_node
                        this.nodes.push(curr_node)
                        curr_node.parent = root
                        return true
                    } else {
                        root = root.left
                    }
                } else {
                    console.log('invalid node: ', node)
                    return false
                }
            }
        }
    };

    BinaryTree.prototype.serialization = function() {
        const root = this.root
        const ret = [gen_node_data(root)]
        const map = {}
        right_left_root(root)

        return ret

        function handler(node) {
            let isLeaf = true
            if (node.right && map[node.right.id]) {
                isLeaf = false
                let right_node = map[node.right.id]
                const curr_node = gen_node_data(node)

                if (node.right.left) {
                    curr_node.children = map['pid' + node.id]
                } else {
                    curr_node.children.push(right_node)
                }
                map[node.id] = curr_node
            }
            if (node.left && map[node.left.id]) {
                isLeaf = false
                const key = 'pid' + node.pid
                const curr_node = map[node.id] ? map[node.id] : gen_node_data(node)
                map[node.id] = curr_node

                let ret = map[key]
                const left_node = map[node.left.id]
                if (ret) {
                    map[key].unshift(curr_node)
                } else {
                    map[key] = [curr_node, left_node]
                }
            }
            if (isLeaf) {
                map[node.id] = gen_node_data(node)
            }
            if (node.depth === 2) {
                ret[0].children.unshift(map[node.id])
            }
        }

        function gen_node_data(node) {
            return {
                id: node.id,
                pid: node.pid,
                label: node.label,
                depth: node.depth,
                children: []
            }
        }

        function right_left_root(node) {
            if (!node)
                return
            right_left_root(node.right)
            right_left_root(node.left)
            handler(node)
        }

    }

    const btree = new BinaryTree()

    for (let item of list) {
        btree.insert(item)
    }

    return btree.serialization()
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
测试代码
const list = [
  {id: 1,  pid: 0,  label:"1",       depth: 1},
  {id: 2,  pid: 1,  label:"1-1",     depth: 2},
  {id: 3,  pid: 1,  label:"1-2",     depth: 2},
  {id: 4,  pid: 1,  label:"1-3",     depth: 2},
  {id: 5,  pid: 3,  label:"1-2-1",   depth: 3},
  {id: 6,  pid: 4,  label:"1-3-1",   depth: 3},
  {id: 7,  pid: 5,  label:"1-2-1-1", depth: 4},
  {id: 8,  pid: 4,  label:"1-3-2",   depth: 3},
  {id: 9,  pid: 3,  label:"1-2-2",   depth: 3},
  {id: 10, pid: 8,  label:"1-3-2-1", depth: 4},
]
const ret = transListToJsonTree(list)

console.log(JSON.stringify(ret, null, 2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

-> 总结

  1. 父节点肯定在子节点前面
  2. 子节点的depth属性表示了嵌套深度
  3. 从而联想到使用二叉树来解决该问题……

但一个目录节点下会存在多个子节点,因此严格来说其实不属于二叉树的结构。 又不想引进更复杂的 b+树,故强行将其改良成一棵自定义二叉树:

  • 左节点表示同级节点,如存在多个同级节点,均顺序左移
  • 右节点为下级子节点

按照这个定义就满足二叉树结构了,但插入节点的方法需要重写。遍历的方法不变。
从而把序列化的问题转换为二叉树遍历的问题。
准确点说,这里需要使用 后序遍历 :从右到左再到根节点,先叶子节点再分支节点。

如果仅仅是序列化的问题,有更简洁的解法如下:

const transListToJsonTree = function(list) {
    return list.filter(node => {
        node.children = list.filter(child => node.id == child.pid);
        return node.pid == 0; 
    });
}
1
2
3
4
5
6

用 for循环实现如下:

const transListToJsonTree = function(arr) {
    for(let i =0; i<arr.length; i++){
        const curr = arr[i]
        curr.children = []
        for(let j=i+1; j<arr.length;j++){
            const node = arr[j]
            if(curr.id === node.pid)
                curr.children.push(node)
        }
    }
    return arr[0]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
编辑此页 (opens new window)
更新于: 2019-07-08 17:45
在排序数组中查找元素的第一个和最后一个位置
走格子

← 在排序数组中查找元素的第一个和最后一个位置 走格子→

Copyright © 2019-2022 | yxxy | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式