297. Serialize and Deserialize Binary Tree

Hard

Problem:

Implement the functionality to serialize a binary tree into an array and, conversely, deserialize it.

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Solution:

All trees can be represented as arrays.

If you know the index of a particular node, you can immediately determine its depth and where its parent and child nodes are located in the array. Even if it's not a complete binary tree, empty positions can be represented as Null. Typically, when expressing a tree as an array, indices start from 1 for easier computation.

BFS

Without exception case in the deserialize method, the function would try to create a root node with the value of #, which is not a valid integer and would cause an error.

By checking for this special case at the beginning of the deserialize method, we can immediately return None to represent an empty tree without trying to process the rest of the string. This ensures that the deserialization process can handle all possible serialized strings, including the special case of an empty tree.

# 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
        """
        queue = collections.deque([root])
        result = ['#']
        while queue:
            node = queue.popleft()
            if node:
                queue.append(node.left)
                queue.append(node.right)
                result.append(str(node.val))
            else:
                result.append("#")
        return ' '.join(result)


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

        root = TreeNode(int(nodes[1]))
        queue = collections.deque([root])
        index = 2

        while queue:
            node = queue.popleft()
            if nodes[index] is not "#":
                node.left = TreeNode(int(nodes[index]))
                queue.append(node.left)
            index += 1
            if nodes[index] is not "#":
                node.right = TreeNode(int(nodes[index]))
                queue.append(node.right)
            index += 1
        
        return root

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