剑指offer37.序列化和反序列化二叉树（详解）

难度：困难
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/submissions/
题目：
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

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

这道题虽然是一道困难题，但是，必须要掌握，其实不难，主要是把两个题合并成一个题。
序列化（serialize）：
看题目可以知道，序列化其实就是层次遍历(bfs)树，将结果输出为一个String字符串，不同的是之前在bfs时，null节点是直接忽略的，现在只不过是也要把null给输出，换汤不换药。
代码：

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        String res =  new String();//存储结果的字符串
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//队列，bfs时使用
        queue.add(root);
        res = "["+root.val;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left != null){
                queue.add(node.left);
                res +=","+node.left.val;
            }else{//节点为空的时候也需要存储到res中
                res += ",null";
            }
            if(node.right != null){
                queue.add(node.right);
                res += ","+node.right.val;
            }else{
                res +=",null";
            }
        }
        res += "]";//最后别忘了加上中括号
        return res;
    }

反序列化:
顾名思义，反序列化就是给定一个String字符串，转化为树的结构，当然字符串是树前序遍历的，所以我们可以知道字符串第一个位置就是根节点，之前我们学过树层次遍历存储在数组中的对应关系，当根节点为i=0的位置时，它的左孩子为2i+1的位置，右孩子为2i+2的位置，依次类推，我们可以得到数组中的结构关系，也就能得到一个二叉树。那么，给我们一个前序遍历的字符串，我们该怎么处理呢？

第一步：我们首先要去掉左右两边的"[“和”]"符号吧，其次，需要把字符串按照“，”进行切分成数组，这样才可以比较没给位置的值，也就是下面这一行代码：

第二步：切分完了之后我们该干什么呢？当然是先建立一个根节点啊

第三步：Ok,根节点有了，就剩左右指针挂载节点了，我们使用bfs遍历的方式进行挂载，判断左右孩子存不存在（通过equals）来构造一颗二叉树。这边i的功能就是指向数组的位置，也就是之前说的2i+1和2i+2。怎么做到呢？直接i++递增就可以。

第四步：返回root节点。

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        //去除，String的[],按照“，”切分
        String[] str = data.substring(1,data.length()-1).split(",");
        //建立第一个根节点
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
        int i=1;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//建立队列的目的，就是层次遍历，添加数据
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            //添加位置数据，以2*i+1 和2*i+2;这里直接递增
            if(!str[i].equals("null")){
                node.left = new TreeNode(Integer.parseInt(str[i]));//创造结点
                queue.add(node.left);//添加到队列中
            }
            i++;//后移一位
            if(!str[i].equals("null")){
                node.right = new TreeNode(Integer.parseInt(str[i]));
                queue.add(node.right);//加到队列
            }
            i++;//后移一位 
        }
        return root;
    }

所以，反序列化也不难吧，思路就是现有前序遍历的数组，然后造一个根节点；之后使用队列的方式一次判断节点的左右孩子存不存在，最后，返回一个root节点。

这道题完成代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        String res =  new String();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        res = "["+root.val;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left != null){
                queue.add(node.left);
                res +=","+node.left.val;
            }else{
                res += ",null";
            }
            if(node.right != null){
                queue.add(node.right);
                res += ","+node.right.val;
            }else{
                res +=",null";
            }
        }
        res += "]";
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        //去除，String的[],按照“，”切分
        String[] str = data.substring(1,data.length()-1).split(",");
        //建立第一个根节点
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
        int i=1;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//建立队列的目的，就是层次遍历，添加数据
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            //添加位置数据，以2*i+1 和2*i+2;这里直接递增
            if(!str[i].equals("null")){
                node.left = new TreeNode(Integer.parseInt(str[i]));//创造结点
                queue.add(node.left);//添加到队列中
            }
            i++;//后移一位
            if(!str[i].equals("null")){
                node.right = new TreeNode(Integer.parseInt(str[i]));
                queue.add(node.right);//加到队列
            }
            i++;//后移一位 
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

本文地址：https://blog.csdn.net/weixin_40392620/article/details/107338538