前序遍历

不使用类全局变量

class Codec:

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

        :type root: TreeNode
        :rtype: str
        """
        # 前序遍历
        res = []
        if not root: 
            res.append('Null')
        else:
            res.append(root.val)
            res += self.serialize(root.left) # 不能用append，否则相当于列表套列表
            res += self.serialize(root.right)
        return res




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

        :type data: str
        :rtype: TreeNode
        """
        return self.dfs(data)

    def dfs(self, data):
        if not len(data): return None
        if data[0] == 'Null':
            data.pop(0)
            return None
        root = TreeNode(data.pop(0)) # 取当前序列第一个数为根节点
        root.left = self.dfs(data)
        root.right = self.dfs(data)
        return root


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

# 若只有前序遍历，并不能唯一确定一棵二叉树
# 前序加中序遍历，就可以唯一确定一个二叉树

使用类全局变量

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

        :type root: TreeNode
        :rtype: str
        """
        self.res = []
        return self.pre_order(root)

    def pre_order(self, root):
        if not root:
            self.res.append('null')
        else:
            self.res.append(root.val)
            self.res = self.pre_order(root.left)
            self.res = self.pre_order(root.right)

        return self.res

    def deserialize(self, data):
        return self.reconstructTree_preorder(data[:-1]) # 此处去掉data最后一个元素，必为Null

    def reconstructTree_preorder(self, data):
        if len(data) == 0: return None
        if data[0] == 'null': 
            data.pop(0)
            return None

        root = TreeNode(data.pop(0)) # 取第一个数为根节点
        root.left = self.reconstructTree_preorder(data)
        root.right = self.reconstructTree_preorder(data)
        return root

层次遍历

class Solution():
    def serialize(self, root):
        if not root: return []
        q = [root]
        while q:
            temp = q.pop(0)
            if not temp: # 当队头节点为空
                res.append('null')
            else:
                res.append(temp.val)  # 输出成层序遍历序列
                q.append(temp.left)
                q.append(temp.right)
        return res

    def deserialize(self, data):
        if len(data) == 0: return None
        if data[0] == 'null': return None
        root = TreeNode(data.pop(0)) # 取第一个数为根节点
        q = [root]
        isLeft = True # 从左开始读数，使用状态变量记录当前节点的右节点是否已经生成，从而判断是否需要出队

        while data:
            temp = data.pop(0) 
            if temp != 'null': 
                node = TreeNode(temp) 
                q.append(node)
                if isLeft:
                    q[0].left = node 
                else:
                    q[0].right = node
            if not isLeft: # 每次isLeft为False，表明生成一个右节点（或遍历到空右节点），则当前根节点已经遍历完毕，需要从队列删除
                q.pop(0)
            isLeft = not isLeft
        return root