BFS

序列化就是广度优先遍历，用的队列实现，时间复杂度$O(n)$，空间复杂度$O(n)$（可以是$O(1)$，但是这样写的顺手）

def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        q = Queue()
        res = []
        if root == None:
            return "[" + "" + "]"
        q.put(root)
        while q.qsize():
            top = q.get()
            if top != None:
                res.append(top.val)
                q.put(top.left)
                q.put(top.right)
            else:
                res.append(None)

        res_str = []
        for x in res:
            if x == None:
                res_str.append('null')
            else:
                res_str.append(str(x))

        return "[" + ", ".join(res_str) + "]"

反序列化，我的做法没有用递归，对于一个广度优先遍历的序列来说，假如这棵树是个完全二叉树，那么第$k$个结点的左儿子下标为$2k+1$，右儿子下标为$2k+2$。假如不是一颗完全二叉树，那么这个规律得稍作改变，因为每一层的$null$（我们就假设它存在，是个TreeNode）在下一层是没有左右儿子的，这样的结点在除最后一层外每存在一个，其后面结点在寻找左右儿子时，儿子们的下标索引就要$-2$，我们设置一个$t$来记录这段偏移量，每扫到一个$null$，我们就$t-=2$。最后一个卡住的地方就是建立二叉树的时候，我的解决方式是先把所有的结点全创建了，然后在它们之间“穿针引线”。时间复杂度$O(n)$

def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if data == None:
            return None
        data = data[1:-1]
        if data == "":
            return None
        data = data.split(', ')
        data_list = []
        for x in data:
            if x == 'null':
                data_list.append(None)
            else:
                data_list.append(TreeNode(int(x)))

        k, t, l, r, n = 0, 0, 1, 2, len(data_list)
        while (k<n) and (r<n):
            cur = data_list[k]
            if cur == None:
                t += 2
            else:
                l = 2 * k + 1 - t
                r = 2 * k + 2 - t
                if data_list[l] != None:
                    cur.left = data_list[l]
                if data_list[r] != None:
                    cur.right = data_list[r]
            k += 1

        root = data_list[0]

        return root