3.5 Serialize and Deserialize Binary Tree

Description

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.

Method

The core to solve this problem is that we need to find a suitable data structure to store nodes' value. we can use "null" to mark the null pointer and then use "#" as split sign for nodes and then traversal the tree by inroder recursion when we deserialize it , we only need to spilt the string into a list of nodes and then construct the tree by recursion.

Time and Space Complexity

serialize: o(n) deserialize : o(n + n)

Code

public class Codec {

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
       return serialize(root,new StringBuilder()).toString();

}

public StringBuilder serialize(TreeNode root, StringBuilder sb){
       if (root == null){
           return sb.append("null").append("#");
       }
       sb.append(root.val).append("#");
       serialize(root.left, sb);
       serialize(root.right, sb);
       return sb;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
       LinkedList<String> stack = new LinkedList<String>(Arrays.asList(data.split("#")));
       return desrialize(stack);
}

public TreeNode desrialize(LinkedList<String> stack){
       String cur = stack.pop();
       if (cur.equals("null")){
           return null;
       }
       int val = Integer.parseInt(cur);
       TreeNode root = new TreeNode(val);
       root.left = desrialize(stack);
       root.right = desrialize(stack);
       return root;
}

}