/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
// 一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构
// 序列化，层序遍历。反序列化，去除首尾"[]"，将字符串按照","划分，采用层序遍历的方式，还原树
// 层序遍历
public class Codec {
  
    // 序列化，层序遍历树。需要注意的是：在结尾删除","
    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        Queue<TreeNode> que = new LinkedList<>();
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        que.offer(root);
        while (!que.isEmpty()) {
            TreeNode tmp = que.poll();
            if (tmp != null) {
                que.offer(tmp.left);
                que.offer(tmp.right); // 这里最终的结果会多出几个null值，对于序列化二叉树没有任何影响
                sb.append(tmp.val + ",");
            } else {
                sb.append("null,"); 
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    // 用split方法划分，将字符串划分为一个字符串数组
    // 字符串转为Integer的方法  Integer.parseInt();
    public TreeNode deserialize(String data) {
       if (data.equals("[]")) {
            return null;
       }
       String[] val = data.substring(1, data.length() - 1).split(",");
       TreeNode root = new TreeNode(Integer.parseInt(val[0]));
       Queue<TreeNode> que = new LinkedList<>();
       que.offer(root);
       int i = 1;
       while (!que.isEmpty()) {
            TreeNode tmp = que.poll();
            if (!val[i].equals("null")) {
                tmp.left = new TreeNode(Integer.parseInt(val[i]));
                que.offer(tmp.left);
            } 
            i++;
            if (!val[i].equals("null")) {
                tmp.right = new TreeNode(Integer.parseInt(val[i]));
                que.offer(tmp.right);
            }
            i++;
        }
        return root;
    }
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));