Idea: I feel like this question is quite important and useful, for its wild range of skills and usage in real life.

The "#" is used to represent none (empty node); meanwhile,
"," works as a symbol to split the return string.

Breath first search works as the traversal method since we are able to use 2i+1 and 2i+2 as the pointer to its children.

The most crucial thing in deserialize is that left = 2*(i-num) + 1, where num is the number of "#" in front of data[i]. It could a little bit hard to think it out, but always remember the recursion in this equation.more

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""


class Solution:
    """
    @param root: An object of TreeNode, denote the root of the binary tree.
    This method will be invoked first, you should design your own algorithm 
    to serialize a binary tree which denote by a root node to a string which
    can be easily deserialized by your own "deserialize" method later.
    """
    def serialize(self, root):
        # a return object
        string =""
        # work for bfs
        queue = []
        # when root is none
        if not root:
            return root
        
        while True:
            # root is str type
            if isinstance(root, str):
                string = string + "#" + ","
                # queue is empty, jump out
                if not queue:
                    string = string + "#" + ","
                    break
                # queue is not empty, pop out next
                else:
                    root = queue.pop(0)
                    continue
                
            # root is TreeNode type
            else:
                string = string + str(root.val) + ","
                
            # there is a non-empty left node
            if root.left:
                left = root.left
            else:
                left = "#"
            # enqueue
            queue.append(left)
            
            # there is a non-empty right node
            if root.right:
                right = root.right
            else:
                right = "#"
            # enqueue
            queue.append(right)
            # pop out next
            root = queue.pop(0)
        
        return string
        
    """
    @param data: A string serialized by your serialize method.
    This method will be invoked second, the argument data is what exactly
    you serialized at method "serialize", that means the data is not given by
    system, it's given by your own serialize method. So the format of data is
    designed by yourself, and deserialize it here as you serialize it in 
    "serialize" method.
    """
    def deserialize(self, data):
        # when data is none
        if not data:
            return data
            
        # number of "#"
        num = 0 
        # listfy the data
        data = data.split(",")
        # build the head node
        node = TreeNode(data[0])
        # deposite root for return
        root = node
        # work for bfs
        queue = []
        
        for i in range(0,len(data)):
            # grab the val
            val = data[i]
            # record the numbers of "#" and ignore it
            if val == "#":
                num +=1
                continue
            
            # do the math to have the left node position
            l = 2*(i-num) + 1
            val = data[l]
            if val != "#":
                left = TreeNode(val)
                node.left = left
                queue.append(left)
             
            # do the math to have the right node position
            r = 2*(i-num) + 2
            val = data[r]
            if val != "#":
                right = TreeNode(val)
                node.right = right
                queue.append(right)
            
            # queue is not empty, pop out next
            if queue:
                node = queue.pop(0)
            # queue is empty, finish the loop
            else:
                break
                
        return root