Skip to main content

Serialize and Deserialize Binary Tree

Question​

Given a binary tree, write a function to serialize it into a string representation and deserialize it back into its original tree structure.

Example 1
None

Solution​

all//Serialize and Deserialize Binary Tree.py


# 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 ""
        ser_list = []
        queue = [root]
        while queue:
            curr = queue.pop(0)
            if curr:
                ser_list.append(str(curr.val))
                queue.append(curr.left)
                queue.append(curr.right)
            else:
                ser_list.append("#")
        return ",".join(ser_list)

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

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        ser_list = data.split(",")
        root = TreeNode(int(ser_list[0]))
        queue = [root]
        i = 1
        while queue and i<len(ser_list):
            curr = queue.pop(0)
            if ser_list[i] != "#":
                curr.left = TreeNode(int(ser_list[i]))
                queue.append(curr.left)
            i+=1
            if ser_list[i] != "#":
                curr.right = TreeNode(int(ser_list[i]))
                queue.append(curr.right)
            i+=1
        return root

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