297. Serialize and Deserialize Binary Tree

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Codec {
11 
12     // Encodes a tree to a single string.
13     public String serialize(TreeNode root) {
14         if (root == null) return "";
15         Queue<TreeNode> queue = new LinkedList<>();
16         queue.offer(root);
17         int size = queue.size();
18         StringBuilder sb = new StringBuilder();
19         while(!queue.isEmpty()){
20             for(int i = 0; i < size; i++){
21                 TreeNode node = queue.poll();
22                 if(node != null){
23                     sb.append(node.val);
24                     sb.append(" ");
25                 }else{
26                     sb.append("n ");
27                     continue;
28                 }
29                 
30                 queue.offer(node.left);
31                 queue.offer(node.right);
32             }
33             size = queue.size();
34         }
35         return sb.toString();
36     
37         
38     }
39 
40     // Decodes your encoded data to tree.
41     public TreeNode deserialize(String data) {
42         if(data.length() == 0) return null;
43         String[] strs = data.trim().split(" ");
44         Queue<TreeNode> queue = new LinkedList<>();
45         TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
46         queue.offer(root);
47         int size = queue.size();
48         int index = 1;
49         while(!queue.isEmpty()){
50             for(int i = 0; i < size; i++){
51                 TreeNode node = queue.poll();
52                 if(strs[index].equals("n")){
53                     node.left = null;
54                     index++;
55                 }else{
56                     TreeNode left = new TreeNode(Integer.parseInt(strs[index]));
57                     node.left = left;
58                     queue.offer(left);
59                     index++;
60                 }
61                 if(strs[index].equals("n")){
62                     node.right = null;
63                     index++;
64                 }else{
65                     TreeNode right = new TreeNode(Integer.parseInt(strs[index]));
66                     node.right = right;
67                     queue.offer(right);
68                     index++;
69                 }
70             }
71             size = queue.size();
72         }
73         return root;
74     }
75 }
76 
77 // Your Codec object will be instantiated and called as such:
78 // Codec codec = new Codec();
79 // codec.deserialize(codec.serialize(root));