pylist

297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Constraints:

Solution

Code Steps

# 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
        """
        # corner case
        if root is None:
            return ""
        # regular case
        out = [str(root.val)] # append value when enqueue
        q = deque([root]) # put root in queue
        while q: # while queue not empty
            # pop
            node = q.popleft()
            # children
            for attr in ['left', 'right']:
                if getattr(node, attr) is None:
                    # corner case
                    out.append('*')
                else:
                    # regular case
                    ## Process the child
                    out.append(str(getattr(node, attr).val)) # append value when enqueue
                    ## append the child
                    q.append(getattr(node, attr))
        return ','.join(out) # list to string
        
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        # corner case
        if data == "":
            return None
        # regular case
        data = data.split(',') # string to list
        root = TreeNode(int(data[0])) # create node when enqueue
        q = deque([root]) # put root in queue
        i = 1 # index of data
        while q: # while queue not empty
            # pop
            node = q.popleft() 
            # children
            for attr in ['left', 'right']:
                # corner case dealt with default value
                if data[i] != '*':
                    # regular case
                    ## Process
                    setattr(node, attr, TreeNode(int(data[i]))) # create node when enqueue
                    ## append the child
                    q.append(getattr(node, attr))
                i += 1 # move data index forward
        return root # return root

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

思路

python 细节