import java.util.*;
public class Solution {
  //采用StringBuilder就是方便给字符串增删
    private void SerializeFunction(TreeNode root, StringBuilder str) {
        if(root==null){
            str.append('#');
            return;
        }
	  //节点不为空，则将内容加到字符串中并以！结尾
        str.append(root.val).append('!');
        SerializeFunction(root.left,str);
        SerializeFunction(root.right,str);
    }
    public String Serialize(TreeNode root) {
        if(root==null){
            return "#";
        }
        StringBuilder res = new StringBuilder();
        SerializeFunction(root, res);
        return res.toString();
    }
    public int index = 0; //字符串下标，方便遍历
    private TreeNode DeserializeFunction(String str) {
        if(str.charAt(index)=='#'){//空字符返回空节点，下标后移
            index++;
            return null;
        }
        int val = 0;
        //遇到分隔符之间是一个完整的数字
        while(str.charAt(index) != '!' && index != str.length()){
            val = val*10 + str.charAt(index) - '0';
            index++;
        }
	  //新增一个节点
        TreeNode root = new TreeNode(val);
        //遍历到字符串结尾，二叉树构建完成
        if(index == str.length()){
            return root;
        }else{//继续遍历字符串
            index++;
        }
        root.left = DeserializeFunction(str);
        root.right = DeserializeFunction(str);
        return root;
    }
    public TreeNode Deserialize(String str) {
        if(str.equals("#")){
            return null;
        }
        TreeNode res = DeserializeFunction(str); 
        return res;
    }
}

方法：前序遍历

我们可以采用前序遍历实现，序列化就是取值存入字符串，遇到空节点则存入’#‘，为了方便反序列化时数字字符串还原为数字，在后面添加’！‘分割。反序列化就是根据序列化的顺序如先序遍历的方式还原二叉树，从字符串中取字符，若为’#‘则构建一个空节点，否则取数字构建新结点，然后遍历左右子树。

序列化

1、树空，直接返回”#“字符串。

2、不空则调用序列化函数，传入根节点和一个可对字符串增删的类型的字符串。

3、在子函数中，采用递归遍历。若当前结点为空，给字符串添加’#‘字符然后返回。否则添加 结点值 和 ！字符。然后左子树递归、右子树递归。

4、最后在主函数，将这个字符串转为普通字符串类型再返回

反序列化

1、需要设置一个全局变量作为字符串的下标

2、字符串只有”#“，则说明原来为空树，返回null。

3、否则调用反序列化函数返回二叉树。

4、子函数中，若遇到’#‘字符，让下标 加一 再返回空。若为数字字符则转为数字再新建节点，转换判断条件就是是否遇到’！‘字符。向下递归将返回值作为新结点的左右孩子，最后返回根节点。

5、主函数中将根节点返回。