算法

(bfs) $O(n)$

这个题要求我们实现两个函数，分别是序列化与反序列化。序列化其实就是编码器，它的功能就是给你一颗二叉树，然后把这颗二叉树编码成字符串。反序列化其实就是解码器，它的功能就是以刚刚编码器返回给我的字符串作为唯一知道的信息，然后把这个字符串重新构建成我们原先的二叉树。

这题采用$dfs/bfs$都行。这里只考虑最暴力的$bfs$的解法，因为看起来通俗易懂。

时间复杂度

时间复杂度为$O(n)$，其中$n$为二叉树中节点的个数。

Java 代码

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        // tree: [v1, v2, null, ...]
        // node: ,
        // val: str(val)
        // null: "null"
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.remove();
            if (cur == null) res.append("null,");
            else {
                res.append(cur.val + ",");
                queue.add(cur.left);
                queue.add(cur.right);
            }
        }
        res.setLength(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.substring(1, data.length() - 1).split(",");

        TreeNode root = getNode(nodes[0]);
        Queue<TreeNode> parents = new LinkedList();
        TreeNode parent = root;
        boolean isLeft = true;
        for (int i = 1; i < nodes.length; ++i) {
            TreeNode cur = getNode(nodes[i]);
            if (isLeft) parent.left = cur;
            else parent.right = cur;
            if (cur != null) parents.add(cur);
            isLeft = !isLeft;
            if (isLeft) {
                parent = parents.peek();
                parents.poll();
            }
        }

        return root;
    }

    private TreeNode getNode(String val) {
        if (val.equals("null")) return null;
        return new TreeNode(Integer.valueOf(val));
    }
}