剑指 Offer 37. 序列化二叉树

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

1.序列化
层序遍历二叉树,将遍历结果放到队列里
2.反序列化
依次弹出队列中的元素,生成每一层元素
使用另一个队列,记录每一层的节点

1.序列化

    public Queue serialize(TreeNode root) {
        Queue ans=new LinkedList<>();
        Queue que=new LinkedList<>();
        if(root==null){
            ans.add(null);
            return ans;
        }
        ans.add(String.valueOf(root.val));
        que.add(root);
        while(!que.isEmpty()){
            root=que.poll();
            if(root.left!=null){
                ans.add(String.valueOf(root.left.val));
                que.add(root.left);
            }else{
                ans.add(null);
            }
            if(root.right!=null){
                ans.add(String.valueOf(root.right.val));
                que.add(root.right);
            }else{
                ans.add(null);
            }
        }
        return ans;
    }

2.反序列化

    public TreeNode deserialize(Queue data) {
        if(data==null||data.size()==0){
            return null;
        }
        TreeNode head=generateNode(data.poll());
        if(head==null){
            return head;
        }
        Queue que=new LinkedList<>();
        que.add(head);
        TreeNode node=null;
        while(!que.isEmpty()){
            node=que.poll();
            node.left=generateNode(data.poll());
            node.right=generateNode(data.poll());
            if(node.left!=null){
                que.add(node.left);
            }
            if(node.right!=null){
                que.add(node.right);
            }
        }
        return head;
    }
    public TreeNode generateNode(String str){
        if(str==null){
            return null;
        }
        return new TreeNode(Integer.valueOf(str));
    }