二叉树的序列化与反序列化 (Python)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        dq = collections.deque()
        dq.append(root)
        res_list = []
        while dq:
            tmp = dq.popleft()
            # 此处判断是因为 为None的左右子节点也需要序列化
            if tmp:
                res_list.append(str(tmp.val))
                # 此处不判空 直接将左右子节点加入dq
                dq.append(tmp.left)
                dq.append(tmp.right)
            else:
                # None节点特殊标记
                res_list.append('X')
        return ','.join(res_list)


        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        data_dq = collections.deque(data.split(',')) 
        if not data_dq:
            return None
        root_val = data_dq.popleft()
        if root_val == 'X':
            return None
        root = TreeNode(root_val)
        # 因为是bfs 所以 dq和data_dq 有奇妙的对应关系：dq 第一个节点的左右子节点为 data_dq的前两个值
        dq = collections.deque()
        dq.append(root)
        while dq:
            node = dq.popleft()
            if data_dq:
                left_val = data_dq.popleft()
                if left_val != 'X':
                    node.left = TreeNode(int(left_val))
                    dq.append(node.left)
            if data_dq:
                right_val = data_dq.popleft()
                if right_val != 'X':
                    node.right = TreeNode(int(right_val))
                    dq.append(node.right)
        return root