力扣labuladong——一刷day34

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

要说序列化和反序列化，得先从 JSON 数据格式说起。 JSON 的运用非常广泛，比如我们经常将变成语言中的结构体序列化成JSON 字符串，存入缓存或者通过网络发送给远端服务，消费者接受JSON 字符串然后进行反序列化，就可以得到原始数据了。 这就是序列化和反序列化的目的，以某种特定格式组织数据，使得数据可以独立于编程语言。 那么假设现在有一棵用 Java 实现的二叉树，我想把它通过某些方式存储下来，然后用 C++ 读取这棵并还原这棵二叉树的结构，怎么办？这就需要对二叉树进行序列化和反序列化了。

前言

---

一、力扣297. 二叉树的序列化与反序列化

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    String SEP = ",";
    String NULL = "#";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root,sb);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> list = new LinkedList<>();
        for(String s : data.split(SEP)){
            list.add(s);
        }
        return fun(list); 
    }
    public TreeNode fun(LinkedList<String> list){
        if(list.isEmpty()){
            return null;
        }
        String first = list.removeFirst();
        if(first.equals(NULL)){
            return null;
        }
        TreeNode cur = new TreeNode(Integer.parseInt(first));
        cur.left = fun(list);
        cur.right = fun(list);
        return cur;
    }

    public void serialize(TreeNode root, StringBuilder sb){
        if(root == null){
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        serialize(root.left,sb);
        serialize(root.right,sb);
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
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

二、力扣二叉树后序序列化

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "#";
        }
        String l = serialize(root.left);
        String r = serialize(root.right);
        return l + "," + r + "," + root.val;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> list = new LinkedList<>();
        for(String s : data.split(",")){
            list.add(s);
        }
        return fun(list);
    }
    public TreeNode fun(LinkedList<String> list){
        String last = list.removeLast();
        if(last.equals("#")){
            return null;
        }
        TreeNode cur = new TreeNode(Integer.parseInt(last));
        cur.right = fun(list);
        cur.left = fun(list);
        return cur;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
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

三、力扣二叉树层序序列化与反序列化

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> deq = new LinkedList<>();
        deq.offerLast(root);
        while(!deq.isEmpty()){
            int len = deq.size();
            for(int i = 0; i < len; i ++){
                TreeNode cur = deq.pollFirst();
                if(cur == null){
                    sb.append("#").append(",");
                    continue;
                }
                sb.append(cur.val).append(",");
                deq.offerLast(cur.left);
                deq.offerLast(cur.right);
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.isEmpty()){
            return null;
        }
        String[] da = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(da[0]));
        Deque<TreeNode> deq = new ArrayDeque<>();
        int index = 0;
        deq.offerLast(root);
        while(!deq.isEmpty()){
            int len = deq.size();
            for(int i = 0; i < len; i ++){
                TreeNode cur = deq.pollFirst();
                index ++;
                if(!da[index].equals("#")){
                    cur.left = new TreeNode(Integer.parseInt(da[index]));
                    deq.offerLast(cur.left);
                }
                index ++;
                if(!da[index].equals("#")){
                    cur.right = new TreeNode(Integer.parseInt(da[index]));
                    deq.offerLast(cur.right);
                }
            }
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
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