题解 | #序列化二叉树#

时间损耗方面，超过99%的python提交代码 主要使用层次遍历的方式，空节点采用值为-1的节点代替，若一层节点的值均为-1则认为该层不存在。构造树采用了递归的方法，除了判断该节点是否在列表中存在外，通过判断节点的值是否为-1决定是否继续递归构造其子树。

from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return None
        resstr = []
        nodeduilie = [root]
        deep = 1
        while True:
            count = 2 ** (deep - 1)
            # 利用值为-1的节点标记空的位置
            # flag 用来标记一层至少有一个节点，不然就终止
            flag = 0
            for i in range(count):
                tempnode = nodeduilie.pop(0)
                resstr.append(tempnode.val)
                if tempnode.left and tempnode.left.val != -1:
                    nodeduilie.append(tempnode.left)
                    flag = 1
                else:
                    nodeduilie.append(TreeNode(-1))
                if tempnode.right and tempnode.right.val != -1:
                    nodeduilie.append(tempnode.right)
                    flag = 1
                else:
                    nodeduilie.append(TreeNode(-1))
            # flag标志着下一层，是否有真实的节点
            if flag == 0:
                break
            # 标志下次循环的是第几层的节点，用于计算一层的节点数
            deep += 1
        return resstr

    def Deserialize(self, s):
        # write code here
        if not s:
            return None
        root = TreeNode(s[0])

        return self.buildtree(root, s, 0)

    def buildtree(self, root: TreeNode, alist: List[int], n):
        # 根节点是列表中的第n个，它的左孩子则是第2n + 1个，右孩子为第2n+2个
        if 2 * n + 1 > len(alist) - 1:
            return root
        if alist[2 * n + 1] != -1:
            root.left = TreeNode(alist[2 * n + 1])
            root.left = self.buildtree(root.left, alist, 2 * n + 1)
        else:
            root.left = None
        if 2 * n + 2 > len(alist) - 1:
            return root
        if alist[2 * n + 2] != -1:
            root.right = TreeNode(alist[2 * n + 2])
            root.right = self.buildtree(root.right, alist, 2 * n + 2)
        else:
            root.right = None

        return root