【先序遍历】LCR 048. 二叉树的序列化与反序列化

LCR 048. 二叉树的序列化与反序列化

解题思路

• 二叉树的序列化和反序列化主要是针对二叉树进行先序遍历
• 序列化就是很对一个二叉树进行先序遍历 然后遍历到每一个节点 将节点添加
• 反序列化将字符串的每一个字符 都构建一个树节点 先序遍历

/**
 * 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();
    }

    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);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // 字符串 转换为列表  LinkedList 是一个双链表  模仿队列  尾部添加元素  头部删除元素
        LinkedList<String> nodes = new LinkedList<>();

        for(String s: data.split(SEP)){
            nodes.addLast(s);// 尾部添加元素  字符串
        }

        return deserialize(nodes);
    }

    TreeNode deserialize(LinkedList<String> nodes){
        if(nodes.isEmpty()){
            return null;
        }

        // 最左侧就是根节点  头部出队
        String first = nodes.removeFirst();

        if(first.equals(NULL)){
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(first));

        root.left = deserialize(nodes);

        root.right = deserialize(nodes);

        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
70
71
72
73
74
75
76
77