LeetCode.297.Serialize and Deserialize Binary Tree 二叉树的序列化与反序列化

题目描述

297 Serialize and Deserialize Binary Tree
https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

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

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

示例:

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅
请问 “[1, null, 2, 3]” 在二叉树测试用例中代表什么
https://support.leetcode-cn.com/hc/kb/article/1194353/
你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

---

解题过程

队列层次遍历序列化和反序列化

我的实现和官方的二叉树字符串表示完全一样，层次遍历序列，最后一层若全是空则忽略。

序列化和反序列化都是每个树节点只访问一次，所以时间复杂度 O(n)，空间复杂度 O(n)

private static class Codec {
    private String prefix = "[";
    private String suffix = "]";

    // 层次序列化
    public String serialize(TreeNode root) {
        if (null == root) {
            return wrap(Collections.emptyList());
        }
        List<String> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        res.add(String.valueOf(root.val));

        while (!queue.isEmpty()) {
            int levelCount = queue.size();
            boolean hasNonNull = false; // 当前层是否有非 null 结点
            List<String> levelList = new ArrayList<>();
            for (int i = 0; i < levelCount; i++) {
                TreeNode treeNode = queue.poll();
                if (treeNode.left != null) {
                    hasNonNull = true;
                    levelList.add(String.valueOf(treeNode.left.val));
                    queue.offer(treeNode.left);
                } else {
                    levelList.add("null");
                }
                if (treeNode.right != null) {
                    hasNonNull = true;
                    levelList.add(String.valueOf(treeNode.right.val));
                    queue.offer(treeNode.right);
                } else {
                    levelList.add("null");
                }
            }
            // 当前层并非全是 null 时才需要序列化
            if (hasNonNull) {
                res.addAll(levelList);
            }
        }
        return wrap(res);
    }

    // 层次反序列化
    public TreeNode deserialize(String data) {
        data = unWrap(data);
        if (data.equals("")) {
            return null;
        }
        String[] strs = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
        queue.offer(root);

        for (int i = 1; i < strs.length && !queue.isEmpty(); i++) {
            TreeNode treeNode = queue.poll();
            if (!strs[i].equals("null")) {
                TreeNode left = new TreeNode(Integer.parseInt(strs[i]));
                treeNode.left = left;
                queue.offer(left);
            }
            i++;
            if (i < strs.length && !strs[i].equals("null")) {
                TreeNode right = new TreeNode(Integer.parseInt(strs[i]));
                treeNode.right = right;
                queue.offer(right);
            }
        }

        return root;
    }

    private String wrap(List<String> input) {
        return prefix + String.join(",", input) + suffix;
    }

    private String unWrap(String input) {
        return input.substring(1, input.length() - 1);
    }
}

递归先序遍历序列化和反序列化

---

GitHub代码

algorithms/leetcode/leetcode/_297_SerializeAndDeserializeBinaryTree.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_297_SerializeAndDeserializeBinaryTree.java

---