# 使用先序遍历序列化与反序列化二叉树

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder res = new StringBuilder();
        SerializeFunction(root, res);
        return res.toString();
    }

    TreeNode Deserialize(String str) {
        String[] nodes =  str.split("!");
        List<String> nodeList =  new LinkedList<>(Arrays.asList(nodes));
        return rDeserialize(nodeList);
    }

    void SerializeFunction(TreeNode root, StringBuilder res) {
        if (root == null) {
            res.append("#!");
        } else {
            res.append(root.val).append("!");
            SerializeFunction(root.left, res);
            SerializeFunction(root.right, res);
        }
    }

    TreeNode rDeserialize(List<String> nodeList) {
        if (nodeList.get(0).equals("#")) {
            nodeList.remove(0);
            return null;
        }
        TreeNode root =   new TreeNode(Integer.valueOf(nodeList.get(0)));
        nodeList.remove(0);
        root.left = rDeserialize(nodeList);
        root.right = rDeserialize(nodeList);
        return root;
    }
}