剑指OfferJZ61：序列化二叉树-java版

JZ61:请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

假如一棵树共有 2 个结点， 其根结点为 1 ，根结点右子结点为 2 ，没有其他结点。按照上面第一种说法可以序列化为“1,#,2,#,#”，按照上面第二种说法可以序列化为“{0:1,2:2}”，按照上面第三种说法可以序列化为“1,2;2,1”，这三种序列化的结果都包含足以构建一棵与原二叉树完全相同的二叉树的信息

需要注意：

public class jz61 {

    //序列化 二叉树--》字符串
    public static String Serialize(TreeNode root) {
        StringBuilder ans = new StringBuilder("[");
        Queue queue=new LinkedList();
        queue.add(root);//队列 [1,2,3,null,null,4,5]

        int sum=1;//用来记录队列中当前节点及其后面非空节点的个数（控制当前节点的两个null值要不要添加到字符串中）
        while(!queue.isEmpty() && root!=null){
            TreeNode node=queue.poll();//poll移除并返问队列头部的元素,如果队列为空，则返回null
            if(node==null){
                ans.append("null");
            }else {
                ans.append(node.val);
                sum--;
                if (node.left != null) {
                    sum++;
                }
                if (node.right != null) {
                    sum++;
                }
                queue.add(node.left);
                queue.add(node.right);
            }
            if(sum!=0){
                ans.append(",");
            }else {
                break;
            }
        }
        ans.append("]");
        return ans.toString();
    }

    //反序列化 字符串--》二叉树
    public static TreeNode Deserialize(String str) {
        String s=str.substring(1,str.length()-1);//截取子字符串 如：截取[1,2,3,null,null,4,5]的子字符串1,2,3,null,null,4,5
        if("".equals(s)){
            return null;//data="[]"
        }
        String[] a=s.split(",");//把字符串s根据“,”拆成n个部分  1 2 3 null null 4 5
        int index=0;
        Queue queue=new LinkedList();
        TreeNode root=new TreeNode(change(a[index++]));
        queue.add(root);
        while(!queue.isEmpty() && index