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.

Example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode 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.

之前做的

https://shuati.gitbook.io/crack-lintcode/~/edit/drafts/-LM_RrNAJmKu_7KaOQKZ/binary-tree/serialize-and-deserialize-binary-tree

第一遍自己做的，runtime很长，有很多坑 1. serialize时 两端的[ ]，加密完以后最后的null 要去掉 2. deserialize split 数组，index问题，注意别越界

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    public String serialize(TreeNode root) {
        // write your code here
        
        String res = "{";
        
        if(root == null)
            return "{}";
        
        List<TreeNode> treeList = new ArrayList<>();
        
        Queue<TreeNode> queue = new LinkedList<>();
        
        queue.offer(root);
        
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            
            treeList.add(node);
            
            if(node != null){
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        
        while(treeList.get(treeList.size()-1) == null){
            treeList.remove(treeList.size()-1);
        }
        
        res += treeList.get(0).val;
        
      for(int i = 1; i < treeList.size();i++){
          if(treeList.get(i) == null){
              res += ",#";
          }else{
              res += ",";
              res += treeList.get(i).val;
          }
      }
       
      res += "}";
      System.out.println(res);
      return res;
        
        
        
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    public TreeNode deserialize(String data) {
        // write your code here
        
        
        if(data.equals("{}")){
            return null;
        }
        
        
        data = data.substring(1,data.length()-1);
        
        
        String[] s= data.split(",");
        
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        
        Queue<TreeNode> q = new LinkedList<>();
        
        q.offer(root);
        
        int index = 1;
        
        while(!q.isEmpty() && index < s.length){
            TreeNode node = q.poll();
            
            if(node == null){
                continue;
            }
            
            TreeNode left = null;
            TreeNode right = null;
            
            if(index < s.length && !s[index].equals("#")){
                left = new TreeNode(Integer.parseInt(s[index++]));
            }else{
                index++;
            }
            
            if(index < s.length && !s[index].equals("#")){
                right = new TreeNode(Integer.parseInt(s[index++]));
            }else{
                index++;
            }
            
            if(node != null){
                node.left = left;
                node.right = right;
                q.offer(node.left);
                q.offer(node.right);
            }
            
            
        }
        
        return root;
        
    }
}

三刷版本 2个坑，加密时，node为null时 left和right 报异常，解密时while循环内保证i不越界

时间复杂度 和空间复杂度 o(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return "[]";
        
        
        List<TreeNode> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        
        queue.offer(root);
        
        while(!queue.isEmpty()){
            int size = queue.size();
            
            for(int i =0; i < size;i++){
                TreeNode node = queue.poll();
                list.add(node);
                if(node != null){
                    queue.offer(node.left);
                
                    queue.offer(node.right);
                }
                
            }
        }
        
        
        while(list.get(list.size()-1) ==null){
            list.remove(list.size()-1);
        }
        
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        
        builder.append(list.get(0).val);
        
        for(int i = 1; i < list.size();i++){
            builder.append(",");
            
            if(list.get(i) == null){
                builder.append("null");
            }else{
                builder.append(list.get(i).val);
            }
            
        }
        
        builder.append("]");
        
        return builder.toString();
        
        
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0 || data.equals("[]")){
            return null;
        }
            
        
        data = data.substring(1,data.length()-1);
        
        
        String[] strArr = data.split(",");
        
        TreeNode root = new TreeNode(Integer.parseInt(strArr[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        
        queue.offer(root);
        int i = 1;
        
        while(!queue.isEmpty() && i < strArr.length){
            TreeNode node = queue.poll();
            
            TreeNode left = null;
            TreeNode right = null;
            
            if(strArr[i].equals("null")){
                node.left = null;
            }else{
                left = new TreeNode(Integer.parseInt(strArr[i]));
                node.left = left;
                
                queue.offer(left);
                
            }
            
            i++;
            if( i >= strArr.length){
                break;
            }
            if(strArr[i].equals("null")){
                node.right = null;
            }else{
                right = new TreeNode(Integer.parseInt(strArr[i]));
                node.right = right;
                queue.offer(right);
            }
            i++;
        }
        
        
        
        
        return root;
     }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));