Leetcode 297 Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Solution 1: use recursive DFS, pre-order traversal.

 public class Codec {  
   // Encodes a tree to a single string.  
   public String serialize(TreeNode root) {  
     StringBuilder sb=new StringBuilder();  
     dfs(root,sb);  
     return sb.toString();  
   }  
   private void dfs(TreeNode x, StringBuilder sb) {  
     if (x==null) {  
       sb.append("null ");  
       return;  
     }  
     sb.append(String.valueOf(x.val));  
     sb.append(' ');  
     dfs(x.left,sb);  
     dfs(x.right,sb);  
   }  
   // Decodes your encoded data to tree.  
   public TreeNode deserialize(String data) {  
     String[] node=data.split(" ");  
     int[] d=new int[1];  
     return dfs(node,d);  
   }  
   private TreeNode dfs(String[] node, int[] d) {  
     if (node[d[0]].equals("null")) {  
       d[0]++;  
       return null;  
     }  
     TreeNode x=new TreeNode(Integer.valueOf(node[d[0]]));  
     d[0]++;  
     x.left=dfs(node,d);  
     x.right=dfs(node,d);  
     return x;  
   }  
 }  

Solution 2: Use iterative DFS, pre-order traversal.

 public class Codec {  
   // Encodes a tree to a single string.  
   public String serialize(TreeNode root) {  
     StringBuilder sb=new StringBuilder();  
     TreeNode x=root;  
     Deque<TreeNode> stack=new LinkedList<>();  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         sb.append(String.valueOf(x.val));  
         sb.append(' ');  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         sb.append("null ");  
         x=stack.pop();  
         x=x.right;  
       }  
     }  
     return sb.toString();  
   }  
   // Decodes your encoded data to tree.  
   public TreeNode deserialize(String data) {  
     if (data.length()==0) return null;  
     String[] node=data.split(" ");  
     int n=node.length;  
     Deque<TreeNode> stack=new LinkedList<>();  
     TreeNode root=new TreeNode(Integer.valueOf(node[0]));  
     TreeNode x=root;  
     stack.push(x);  
     int i=1;  
     while (i<n) {  
       while (i<n && !node[i].equals("null")) {  
         x.left=new TreeNode(Integer.valueOf(node[i++]));  
         x=x.left;  
         stack.push(x);  
       }  
       while (i<n && node[i].equals("null")) {  
         x=stack.pop();  
         i++;  
       }  
       if (i<n) {  
         x.right=new TreeNode(Integer.valueOf(node[i++]));  
         x=x.right;  
         stack.push(x);  
       }  
     }  
     return root;  
   }  
 }  

Solution 3: Use BFS

 public class Codec {  
   // Encodes a tree to a single string.  
   public String serialize(TreeNode root) {  
     if (root==null) return "";  
     Queue<TreeNode> qu=new LinkedList<>();  
     StringBuilder sb=new StringBuilder();  
     qu.offer(root);  
     sb.append(String.valueOf(root.val));  
     sb.append(' ');  
     while (!qu.isEmpty()) {  
       TreeNode x=qu.poll();  
       if (x.left==null) sb.append("null ");  
       else {  
         qu.offer(x.left);  
         sb.append(String.valueOf(x.left.val));  
         sb.append(' ');  
       }  
       if (x.right==null) sb.append("null ");  
       else {  
         qu.offer(x.right);  
         sb.append(String.valueOf(x.right.val));  
         sb.append(' ');  
       }  
     }  
     return sb.toString();  
   }  
   // Decodes your encoded data to tree.  
   public TreeNode deserialize(String data) {  
     if (data.length()==0) return null;  
     String[] node=data.split(" ");  
     Queue<TreeNode> qu=new LinkedList<>();  
     TreeNode root=new TreeNode(Integer.valueOf(node[0]));  
     qu.offer(root);  
     int i=1;  
     while (!qu.isEmpty()) {  
       Queue<TreeNode> nextQu=new LinkedList<>();  
       while (!qu.isEmpty()) {  
         TreeNode x=qu.poll();  
         if (node[i].equals("null")) x.left=null;  
         else {  
           x.left=new TreeNode(Integer.valueOf(node[i]));  
           nextQu.offer(x.left);  
         }  
         i++;  
         if (node[i].equals("null")) x.right=null;  
         else {  
           x.right=new TreeNode(Integer.valueOf(node[i]));  
           nextQu.offer(x.right);  
         }  
         i++;  
       }  
       qu=nextQu;  
     }  
     return root;  
   }  
 }