题目

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

<pre style="box-sizing: border-box; overflow: auto; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; font-size: 13px; display: block; padding: 9.5px; margin: 0px 0px 10px; line-height: 1.42857; color: rgb(51, 51, 51); word-break: break-all; word-wrap: break-word; background-color: rgb(245, 245, 245); border: 1px solid rgb(204, 204, 204); border-radius: 4px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">   
   1
   / \
  2   3
     / \
    4   5
</pre>

as `"[1,2,3,null,null,4,5]"`, just the same as [how LeetCode OJ serializes a binary tree](https://leetcode.com/faq/#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.

思路

1. preorder遍历进行序列化，"&"代表null；
2. 将前序遍历得到的序列化反序列化，遍历序列化字符串；需要一个全局变量i，来记录遍历到的位置。

代码

public class SerializeandDeserializeBST2 {
    // Encodes a tree to a single string.
    public static String serialize(TreeNode root) {
        String data = "";
        if (root == null) {
            return "&,";
        }
        data += root.val + "," + serialize(root.left) + serialize(root.right);
        return data;
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data == "") {
            return null;
        }
        String[] tmp = data.split(",");
        TreeNode root = dfs(tmp);
        return root;
    }

    private int i = 0;

    public TreeNode dfs(String[] tmp) {
        if (i < 0 || i >= tmp.length) {
            return null;
        }
        String valStr = tmp[i];
        i++;
        if(valStr.equals("&")){
            return null;
        }else{
            int val= Integer.parseInt(valStr);
            TreeNode root = new TreeNode(val);
            root.left = dfs(tmp);
            root.right = dfs(tmp);
            return root;
        }
    }
}

思路

栈前序遍历实现序列化，队列实现反序列化。

代码

public static String serialize(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        StringBuilder sb = new StringBuilder();
        while(!stack.empty()){
            TreeNode current = stack.pop();
            if(current == null){
                sb.append("&").append(",");
            }else{
                sb.append(current.val).append(",");
                stack.push(current.right);
                stack.push(current.left);
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> qstr = new LinkedList<>();
        Collections.addAll(qstr,data.split(","));
        TreeNode root = travle(qstr);
        return root;
    }

    private TreeNode travle(Queue<String> qstr) {
        if(!qstr.isEmpty()){
            TreeNode root = null;
            String val = qstr.poll();
            if(val.equals("&")){
                 root = null;
            }else{
                 root = new TreeNode(Integer.parseInt(val));
                root.left = travle(qstr);
                root.right = travle(qstr);
            }
            return root;
        }
        return null;
    }