题解 |【清晰图解】 #序列化二叉树#重要是思路

默认你已理解题意

那就开始吧

思路如下

我们知道平时使用的前序、中序、后序、层序遍历，遍历过程中记录二叉树的信息是不完整的，也就是说唯一的输出序列可能对应着多种二叉树可能性。我们知道 序列化 和 反序列化 是完全可逆。

所以序列化的字符串能够携带完整的二叉树信息，我就是说的这个意思

1 看懂示例先

我们看一下题目那个例子，序列化的字符串是一个二叉树 “层序遍历”（BFS）的结果，我这里题解也是层序遍历哈图片说明为表示出完整的二叉树，我考虑把叶节点下的 null 也记录下来。在此基础上，对于列表里面任意某节点 node，它的左边子节点 node.left 和右边子节点 node.right 在序列化过程中的位置都是 唯一确定 的,我知道你可能还是懵的，你要仔细看上面的图你就能理解我上面说的话。

我们把上面图的规律总结下来

图片说明

设 m 是列表区间 [0,n] 中的 null 节点个数，那么可以总结下根节点、左边子节点、右边子节点的列表索引递推公式下面这样

图片说明

序列化 我们这里用层序遍历来实现的哈。反序列化 是用上面递推公式反推各节点在序列中的索引，来实现的哈

2 如何序列化

借助队列，对二叉树进行层序遍历，并把越过叶节点的 null 也打印出来。

算法流程如下

特例处理：若 root 为空，则直接返回空列表 "[]" ；
初始化：队列 queue （包含根节点 root ）；序列化列表 res ；
层序遍历：当 queue 为空时跳出； 1）节点出队，记为 node ； 2）若 node 不为空：① 打印字符串 node.val ，② 将左、右子节点加入 queue ； 3）否则（若 node 为空）：打印字符串 "null" ；
返回值：拼接列表，用 ',' 隔开，首尾添加中括号；

复杂度分析下

时间复杂度是O(N) ： NN 为二叉树的节点数，层序遍历需要访问所有节点，最差情况下需要访问 N + 1N+1 个 null ，总体复杂度为 O(2N + 1) = O(N)O(2N+1)=O(N) 。
空间复杂度也是O(N)：最差情况下，队列 queue 同时存储（N+1）/2个节点（或 N+1 个null），使用了 O(N) ；列表 res 也使用 O(N)，如果你还是不理解建议多理解几遍，看下面图是怎么变化的？

3 然后是反序列化

我们先定义的 node , node.left , node.right 这几个结点在序列化列表中的位置关系，就能实现反序列化啦。

前面已经说过，要用队列按层去建一个二叉树，借助一个指针 i 指向节点 node 的左、右两子节点，每建一个 node 的左、右子节点，指针 i 就向右移动 1 位。

流程如下

1. 特例先处理：若 data 为空，直接返回 null ； **2. 然后初始化：序列化列表 vals （先去掉首尾中括号，再用逗号隔开哈），指针 i = 1 ，根节点 root （值为 vals[0] ），队列 queue（已经包含 root ）； 3. 按层构建：当 queue 为空时跳出；

节点出队，记为 node ；
构建 node 的左子节点：node.left 的值为 vals[i] ，并将 node.left 入队；
执行 i += 1 ；
构建 node 的右子节点：node.left 的值为 vals[i] ，并将 node.left 入队；
执行 i += 1 ； 4. 返回值：返回根节点 root 就OK啦；

复杂度分析下

时间复杂度 O(N)： N 为二叉树的节点数，按照层去建二叉树则需要遍历整个 valsvals ，它的长度最大为 2N+1。
空间复杂度 O(N)：最差情况下，队列 queue 能同时存储（N+1）/2个节点，所以使用了O(N)的额外空间，可能第一遍你可能有点不懂没事的，推荐你多看下面是咋变化的你就会恍然大悟 完整代码如下

public class Codec {
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}