Leetcode Problem 297 Serialize and Deserialize Binary Tree.txt

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.

Example: 

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"
Clarification: The above 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.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.



Hint to solve: Use BFS while serialization. Use a double ended queue while deserialization.


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

import collections

class Codec:
    
    def serialize(self, root):
        result = []
        
        currentLevel = []
        children = []
        currentLevel.append(root)
        while len(currentLevel) > 0:
            currentNode = currentLevel.pop(0)
            
            if currentNode != None:
                result.append(currentNode.val)
                children.append(currentNode.left)
                children.append(currentNode.right)
            else:
                result.append(None)
                
            if len(currentLevel) == 0:
                currentLevel = children
                children = []
        
        #print(result)
        return result
        

    def deserialize(self, data):
        if data[0] == None:
            return []
        
        doubleQueue = collections.deque()
        root = TreeNode(data[0])
        doubleQueue.append(root)
        index = 1
        while len(doubleQueue) > 0:
            node = doubleQueue.popleft()
            
            if index < len(data) and data[index] != None:
                node.left = TreeNode(data[index])
                doubleQueue.append(node.left)
            index += 1
            
            if index < len(data) and data[index] != None:
                node.right = TreeNode(data[index])
                doubleQueue.append(node.right)
            index += 1
        
        return root
            

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





Alternate approach using DFS

class Codec:
    
    def custom_serialize(self, root, answer):
        if root == None:
            answer += "None" + ","
        else: 
            answer += str(root.val) + ","
            answer = self.custom_serialize(root.left, answer)
            answer = self.custom_serialize(root.right, answer)
        
        return answer

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if root == None:
            return ""
        answer = self.custom_serialize(root,"")
        print(answer)
        return answer
        
        
    
    def custom_deserialize(self, tokens):
        
        if(len(tokens) == 0):
            return None
        
        if(tokens == None or tokens[0] == "None"):
            tokens.pop(0)
            return None
        else:
            #print(tokens)
            currentToken = tokens[0]
            tokens.pop(0)
            node = TreeNode(currentToken)
            node.left = self.custom_deserialize(tokens)
            node.right = self.custom_deserialize(tokens)
        
        return node        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == "":
            return None
        
        tokens = data.split(',')

        root = TreeNode(tokens[0])
        #print(root)
        return self.custom_deserialize(tokens)