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

雨点打透心脏的1/2处 2023-10-01 08:57 2阅读 0赞

**题目内容：**

![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;
        }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/5bc958140e964e33871b2be322cf5a0f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16