Description

对于一个二叉树进行序列化和反序列化

Solution

使用BFS,按照层插入

# 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
        """
        if root is None:
            return ''
        res = []
        queue =[root]
        while len(queue)>0:
            head = queue.pop(0)
            if head is None:
                res.append('#')
            else:
                res.append(str(head.val))
                queue.append(head.left)
                queue.append(head.right)
        while res[-1] == '#':
            res.pop()
        
        return ','.join(res)

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if len(data) ==0:
            return None
        data = data.split(',')
        data = list(data)
        left = True
        root = TreeNode(int(data[0]))
        queue = [root]
        idx = 0 # pointer to the ele in the queue
        for i in range(1, len(data)):
            if data[i] != '#':
                new_node =TreeNode(int(data[i]))       
                if left is True:
                    queue[idx].left = new_node
                else:
                    queue[idx].right = new_node
                queue.append(new_node)
            if not left:
                idx +=1
            left = not left
        return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))