📃 题目描述

题目链接：

• 剑指 Offer 37. 序列化二叉树 (opens new window)
• 剑指 Offer II 048. 序列化与反序列化二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 297. 二叉树的序列化与反序列化，BFS和DFS双解法 - 二叉树的序列化与反序列化 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

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

🔔 解题思路

层序遍历

首先，在序列化（root -> String）的时候我们需要注意下，正常的层序遍历结果中是不会出现 null 的，但是因为后面需要反序列化，所以我们需要 null 来帮助我们弄清楚二叉树的结构。举个例子：

按照正常层序遍历的结果，两个树的结果都是 6,6,6,6,6

那如果加上 null

• (a) 层序遍历结果：6，6，6，6，6，null，null（这俩 null 可以省略，因为不影响结构）
• (b) 层序遍历结果：6，6，6，null，null，6，6

所以，尽管 null 节点通常没有在图上画出来，但它们对树的结构是至关重要的

对于反序列化，需要注意下，就是这里我们序列化出来的结果其实不是满二叉树那种格式的，什么意思呢，就是如果某个节点是 null 的，那么它的左孩子节点是不会出现在序列化结果里的，举个例子：

反序列化之前在 “如何构造一棵二叉树” 中我们解释过了，这里直接复制过来就行

/**
 * 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 "null";
        }

        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            // null 节点也要加进去
            sb.append(cur == null ? "null" : cur.val);
            sb.append(",");

            // cur 如果是 null 的话，那它的左孩子节点就不用出现在反序列化结果里了
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
        }
        
        // 删除最后一个逗号
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0 || data.equals("null")) {
            return null;
        }

        String[] nodes = data.split(",");
        // TreeNode 集合
        List<TreeNode> list = new ArrayList<>();
        for (String node : nodes) {
            list.add(node.equals("null") ? null : new TreeNode(Integer.parseInt(node)));
        }

        TreeNode root = list.get(0);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // i 指向当前节点 cur 的左子树节点
        int i = 1;
        while (!queue.isEmpty() && i < list.size()) {
            TreeNode cur = queue.poll();
            // 此处不需要进行 cur 的判空，因为队列中不会存储 null 的节点

            cur.left = list.get(i);
            cur.right = list.get(i + 1);
            
            // cur 的左（i）孩子入队
            if (cur.left != null) {
                // cur.left == null 的话，那么 cur.left 的左右孩子也一定为 null，就不用入队构建了
                queue.offer(cur.left);
            }
            // cur 的右（i + 1）孩子入队
            if (cur.right != null) {
                // cur.right == null 的话，那么 cur.right 的左右孩子也一定为 null，就不用入队构建了
                queue.offer(cur.right);
            }

            // 进入下一个节点的左子树节点
            i += 2;
        }

        return root;
    }
}

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

先序遍历

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

    // 前序遍历序列化
    public String serialize(TreeNode root) {
        if (root == null) {
            return "null";
        }

        String leftStr = serialize(root.left);
        String rightStr = serialize(root.right);

        return String.valueOf(root.val) + "," + leftStr + "," + rightStr;
    }

    // 反序列化前序遍历的结果
    public TreeNode deserialize(String data) {
        String[] nodeStrs = data.split(",");
        // nodeStrs 的下标
        int[] index = {0};

        return reconPreOrder(nodeStrs, index);
    }

    private TreeNode reconPreOrder(String[] nodeStrs, int[] index) {
        String str = nodeStrs[index[0]];
        // 注意这个位置必须在下面 if 判断的上面
        index[0] ++;
		
        // 题目是先调用序列化，再调用反序列化，所以根据序列化的结果，这里的判空应该是这种形式
        if (str.equals("null")) {
            return null;
        }

        TreeNode node = new TreeNode(Integer.parseInt(str));
        // 构造左右子树
        node.left = reconPreOrder(nodeStrs, index);
        node.right = reconPreOrder(nodeStrs, index);

        return node;
    }
}

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

递归函数 reconPreOrder 的每次执行都会从字符串数组中取出一个字符串并以此反序列化出一个节点（如果取出的字符串是"null"，则返回null节点）。

我们需要一个下标去扫描字符串数组 nodeStrs 中的每个字符串。通常用一个整数值来表示数组的下标，但在上述代码中却定义了一个长度为1的整数数组 index

这是因为递归函数 reconPreOrder 每反序列化一个节点时下标就会增加 1，并且函数的调用者需要知道下标增加了。如果函数 reconPreOrder 的第2个参数 index 是整数类型，那么即使在函数体内修改 index 的值，修改之后的值也不能传递给它的调用者。但把 index 定义为整数数组之后，可以修改整数数组中的数字，修改之后的数值就能传给它的调用者

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：