序列化二叉树（序列化和反序列化）-蒲公英云

序列化二叉树（序列化和反序列化）

题目内容：

watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16

解题思路：

一，序列化

所谓序列化就是将二叉树的每个结点按照层序遍历的结果输出，这里面也包含空节点，因为这棵二叉树，不一定是一颗完全二叉树
分析到这里序列化就变得简单多了，唯一的难点在于将树编码为单字符串（Encodes a tree to a single string）
因此我们借用于StringBuilder 的特性，可以利用append拼接八大类型的任一种类型，此时选择以字符串类型进行拼接
并在队头结点不等于空的时候进行其子节点的入队列操作

public String serialize(TreeNode root) {
        //如果根节点为空，返回null
        if(root == null){
            return "[]";
        }
        //创建一个StringBuilder的对象sb
        StringBuilder sb = new StringBuilder();
        //根绝返回结果可以知道，需要添加"["
        sb.append("[");
        Queue<TreeNode> q = new LinkedList<>();
        //将头结点入队列
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            //如果此时队头的结点不为空，将其val保存到sb中，并加上","
            if(cur != null){
                //也可以是  sb.append(cur.val + ",");
                sb.append(cur.val).append(",");
                //进行其孩子结点的入队列操作
                q.offer(cur.left);
                q.offer(cur.right);
            }else{
                //如果结点为空，那么就添加"null"
                sb.append("null").append(",");
            }
        }
        //去掉最后一个","
        sb.deleteCharAt(sb.length() - 1);
        //加上"]"
        sb.append("]");
        return sb.toString();
    }

二，反序列化

反序列化就是根据上面的序列化结果来重新创建二叉树
思路还是先将序列化结果分割成字符串数组
以层序遍历的顺序，去取相应的孩子结点，这个取孩子结点需要一个移动的下标来进行遍历

// Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        //如果字符串data的内容和空字符串相等，返回空
        if(data.equals("[]")){
            return null;
        }
        /*
        根绝上面的序列化可以得知，0号位置一定是"["，最后一位一定是"]"
        因此去掉最后一位和第一位，并且将字符串以","处分割为子字符串，以字符串数组返回
        */
        String[] s = data.substring(1,data.length() - 1).split(",");
        Queue<TreeNode> q = new LinkedList<>();
        //将字符串的第一位先定义好，并入队列
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        q.offer(root);
        //后序的i从1开始
        int i = 1;      
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            //如果字符串数组s中的是s[i]不为空，那么就以此字符的值定义cur.left
            if(!s[i].equals("null")){
                cur.left = new TreeNode(Integer.parseInt(s[i]));
                q.offer(cur.left);
            }
            i++;
            if(!s[i].equals("null")){
                cur.right = new TreeNode(Integer.parseInt(s[i]));
                q.offer(cur.right);
            }
            i++;
        }
        return root;
    }