**Serialize and Deserialize Binary Tree

 1 class Solution {
 2     /**
 3      * This method will be invoked first, you should design your own algorithm 
 4      * to serialize a binary tree which denote by a root node to a string which
 5      * can be easily deserialized by your own "deserialize" method later.
 6      */
 7     public String serialize(TreeNode root) {
 8         if (root == null) {
 9             return "{}";
10         }
11 
12         ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
13         queue.add(root);
14 
15         for (int i = 0; i < queue.size(); i++) {
16             TreeNode node = queue.get(i);
17             if (node == null) {
18                 continue;
19             }
20             queue.add(node.left);
21             queue.add(node.right);
22         }
23 
24         while (queue.get(queue.size() - 1) == null) {
25             queue.remove(queue.size() - 1);
26         }
27 
28         StringBuilder sb = new StringBuilder();
29         sb.append("{");
30         sb.append(queue.get(0).val);
31         for (int i = 1; i < queue.size(); i++) {
32             if (queue.get(i) == null) {
33                 sb.append(",#");
34             } else {
35                 sb.append(",");
36                 sb.append(queue.get(i).val);
37             }
38         }
39         sb.append("}");
40         return sb.toString();
41     }
42     
43     /**
44      * This method will be invoked second, the argument data is what exactly
45      * you serialized at method "serialize", that means the data is not given by
46      * system, it‘s given by your own serialize method. So the format of data is
47      * designed by yourself, and deserialize it here as you serialize it in 
48      * "serialize" method.
49      */
50     public TreeNode deserialize(String data) {
51         if (data.equals("{}")) {
52             return null;
53         }
54         String[] vals = data.substring(1, data.length() - 1).split(",");
55         ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
56         TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
57         queue.add(root);
58         int index = 0;
59         boolean isLeftChild = true;
60         for (int i = 1; i < vals.length; i++) {
61             if (!vals[i].equals("#")) {
62                 TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
63                 if (isLeftChild) {
64                     queue.get(index).left = node;
65                 } else {
66                     queue.get(index).right = node;
67                 }
68                 queue.add(node);
69             }
70             if (!isLeftChild) {
71                 index++;
72             }
73             isLeftChild = !isLeftChild;
74         }
75         return root;
76     }
77 }