297. 二叉树的序列化与反序列化

发表于 | 分类于
描述示例

用时：30min

序列化很简单，使用BFS可以解决

反序列化需要用到二叉树的性质，即第 i 个节点的子节点分别为 (i + 1) * 2 - 1 和 ( i + 1) * 2, 流程

  1. 找到父节点，入栈，此时指针 i 在 父节点的 val 上
  2. 父节点出栈，找到父节点的左右节点，指针根据规则找到 两遍的值，左右节点入栈， i++
  3. 重复 1 
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
var serialize = function(root) {
    if (!root) return []
    var que = [root]
    var res = []
    while(que.length) {
        var cur = que.shift()
        if (cur) {
            res.push(cur.val);   
            que.push(cur.left);
            que.push(cur.right); 
        } else {                   
            res.push('null');            
        }  
    }
    return res.join(',')
};


  
/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    if (!data.length) return null
    var nodes = data.split(',')
    var i = 0 
    var root = new TreeNode(nodes[i])
    var que = [root]
    while ( que.length) {
        var node  = que.shift()
        var left = nodes[ (i + 1) * 2 - 1]
        var right = nodes[ (i + 1) * 2]
        if (left !== 'null') {
            node.left = new TreeNode(left)
            que.push(node.left)
        } else {
            node.left = null
        }
        if (right !== 'null') {
            node.right = new TreeNode(right)
            que.push(node.right)
        } else {
            node.right = null
        }
        i++
    }
    return root
};