[Leetcode] 297. Serialize and Deserialize Binary Tree

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: []

Constraints:

The number of nodes in the tree is in the range [0, 10``4``].

-1000 <= Node.val <= 1000

How to understand?

Binary tree can be serialized as string and it will be deserialized as Binary tree.

How to approach?

DFS

class Codec:

    # Serialization

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

        def rserialize(root, string):
            """a recursive helper function for the serialize() function."""
            # check base case
            if root is None:
                string += "None,"
            else:
                string += str(root.val) + ","
                string = rserialize(root.left, string)
                string = rserialize(root.right, string)
            return string

        return rserialize(root, "")

    # Deserialization

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """

        def rdeserialize(l):
            """a recursive helper function for deserialization."""
            if l[0] == "None":
                l.pop(0)
                return None

            root = TreeNode(l[0])
            l.pop(0)
            root.left = rdeserialize(l)
            root.right = rdeserialize(l)
            return root

        data_list = data.split(",")
        root = rdeserialize(data_list)
        return root

serialize

create a function take root and string input.

return the function call with root node and empty string.

in the function, base case will be set to check the node is None, then append the None in the given string.

other than that, check the value and append it to the string, check left node and call the function and then do the same thing for the right node.

lastly return the string.

deserialize

get the string data and create the root node from it.

create the function to use data and return the node from it.

create the list(array) splitting the input data.

create root and call the function using the list.

lastly return the root.

in the function, use the first element in the list.

if the first element is None then pop it out and return None, use this as base case.

intialize root as TreeNode using first element in the list. and then pop it out.

call the function for node.left and node.right. lastly return the root.

BFS

class Codec:
    '''       
    O(n) time and O(n) space, BFS traversal
    
    e.g., 1
         / \
        2   5
       / \
      3   4  , 
    level order traversal, 
    serialize will be '1,2,5,3,4,None,None,None,None,None,None,'; 
    deserialize with queue as well, convert back. Time and Space O(n).
    '''
    def serialize(self, root):
        if not root:
            return ''
        queue = collections.deque()
        queue.append(root)
        res = ''
        while queue:
            node = queue.popleft()
            if not node:
                res += 'None,'
                continue
            res += str(node.val) + ','
            queue.append(node.left)
            queue.append(node.right)
        return res
            
    def deserialize(self, data):
        if not data:
            return None
        ls = data.split(',')
        root = TreeNode(int(ls[0]))
        queue = collections.deque()
        queue.append(root)
        i = 1
        while queue and i < len(ls):
            node = queue.popleft()
            if ls[i] != 'None':
                left = TreeNode(int(ls[i]))
                node.left = left
                queue.append(left)
            i += 1
            if ls[i] != 'None':
                right = TreeNode(int(ls[i]))
                node.right = right
                queue.append(right)
            i += 1
        return root

serialize

use deque(double ended queue), initialize deque with root, and set res as empty string.

while queue has a length, pop the first element in the queue and set it as node.

if the node is None, then append the None to the res string and continue.

if there is value for node then node convert the node.value as string and append it to the res with ","

do the same thing for node.left and node.right. queue will have the all the nodes in the root node in the while iteration.

You can see the queue will have the nodes as level by level.

deserialize

it takes data, and create the TreeNode from data.

base case will be checking data and if it's None then return None.

create ls by splitting data by ","

and create root TreeNode with integer converted using the first element in the list.

and use the queue (double ended queue), append the root in the deque

set i as 1.

while condition to check the queue has length. and i is less than length of the list.

create the node using the first element in the deque.

list's i th element is not None, then create the left using TreeNode with converted integer of list's i the element.

increment i by 1.

and do the same thing for right node.

lastly return the root.

You can see the root is created from the data level by level.