1
public class Codec {
2

3
  // Encodes a tree to a single string.
4
  public String serialize(TreeNode root) {
5
    String data = "";
6
    Queue<TreeNode> q = new LinkedList<>();
7
    if (root != null) q.add(root);
8
    else return "";
9
    data = Integer.toString(root.val) + "e";
10
    while (!q.isEmpty()) {
11
      int size = q.size();
12
      for (int i = 0; i < size; i++) {
13
        TreeNode node = q.poll();
14
        if (node.left != null) {
15
          data = data + Integer.toString(node.left.val) + "e";
16
          q.add(node.left);
17
        } else data = data + "N" + "e";
18
        if (node.right != null) {
19
          data = data + Integer.toString(node.right.val) + "e";
20
          q.add(node.right);
21
        } else data = data + "N" + "e";
22
      }
23
    }
24
    return data;
25
  }
26

27
  // Decodes your encoded data to tree.
28
  public TreeNode deserialize(String data) {
29
    if (data.length() == 0) return null;
30
    int i = 0;
31
    String s = "";
32
    while (data.charAt(i) != 'e') s = s + data.charAt(i++);
33
    int d = Integer.parseInt(s);
34
    TreeNode root = new TreeNode(d);
35
    Queue<TreeNode> q = new LinkedList<>();
36
    q.add(root);
37
    while (i < data.length() && !q.isEmpty()) {
38
      int size = q.size();
39
      for (int j = 0; j < size; j++) {
40
        s = "";
41
        i++;
42
        TreeNode node = q.poll();
43
        while (data.charAt(i) != 'e') s = s + data.charAt(i++);
44
        if (s.equals("N")) node.left = null;
45
        else {
46
          TreeNode l = new TreeNode(Integer.parseInt(s));
47
          node.left = l;
48
          q.add(l);
49
        }
50
        s = "";
51
        i++;
52
        while (data.charAt(i) != 'e') s = s + data.charAt(i++);
53
        if (s.equals("N")) node.right = null;
54
        else {
55
          TreeNode r = new TreeNode(Integer.parseInt(s));
56
          node.right = r;
57
          q.add(r);
58
        }
59
      }
60
    }
61
    return root;
62
  }
63
}