LeetCode297.二叉树的序列化和反序列化

题目要求

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

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

提示：

• 树中结点数在范围 [0, 104] 内
• -1000 <= Node.val <= 1000

解题思路

观察可知，二叉树的序列化和反序列化都是通过二叉树的层序遍历进行实现的，所以我们想要解题，就要通过二叉树的层序遍历的性质来进行解题。

遍历数组，当1个节点进入队列的时候，且弹出该节点之时，则当前处理的该节点算是一个根节点。按照层序遍历的特点，我们设有一个i指针。

当弹出节点的时候，i正好位于当前节点的左子结点。i自增1之后，则i处于当前根节点的右子节点中。若非空，则子节点加入栈。

代码解析

/**
 * 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 "[]";
        }
        // 新建一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 新建一个列表
        List<TreeNode> list = new ArrayList<>();
        // 根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                list.add(node);
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                list.add(null);
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        sb.append(list.stream()
                .map(node -> node == null ? "null" : String.valueOf(node.val))
                .collect(Collectors.joining(",")));
        sb.append("]");
        String result = sb.toString();
        return result;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("[]")) {
            return null;
        }
        // 构造值数组
        String[] vals = data.substring(1, data.length() - 1).split(",");
        // 构造队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 构造根节点
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        // 根节点加入队列
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            // 弹出当前根节点
            TreeNode curRoot = queue.poll();
            if (!vals[i].equals("null")) {
                curRoot.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(curRoot.left);
            }
            i++;
            if (!vals[i].equals("null")) {
                curRoot.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(curRoot.right);
            }
            i++;
        }
        return root;
    }
}