LeetCode #297: Serialize and Deserialize Binary Tree

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

The problem requires serializing and deserializing a binary tree. Serialization is the process of converting a data structure into a sequence of bytes or characters that can be stored in a file or transmitted across a network. Deserialization is the reverse process of constructing the data structure from the sequence of bytes or characters.

Algorithm:

1. Define a Codec class that has two methods, serialize and deserialize.
2. In the serialize method, take in a TreeNode as input.
3. If the TreeNode is None, return the string ‘None,’ to indicate a null node.
4. Convert the TreeNode value to a string and concatenate it with a comma separator.
5. Recursively call the serialize method on the left and right children of the TreeNode.
6. Return the concatenated string.
7. In the deserialize method, take in a string as input.
8. Split the string by comma separator to obtain a list of node values.
9. Define a recursive helper function buildTree that takes in the list of node values.
10. If the first element in the list is ‘None’, pop it and return None.
11. Convert the first element to an integer and use it to construct a TreeNode.
12. Recursively call the buildTree function on the left and right children of the TreeNode.
13. Return the TreeNode.
14. Call the buildTree function on the list of node values obtained from splitting the input string and return the resulting TreeNode.

Here is the solution in Python3:

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        if not root:
            return 'None,'
        left = self.serialize(root.left)
        right = self.serialize(root.right)
        return str(root.val) + ',' + left + right

    def deserialize(self, data: str) -> Optional[TreeNode]:
        nodes = data.split(',')
        def buildTree(nodes):
            val = nodes.pop(0)
            if val == 'None':
                return None
            node = TreeNode(int(val))
            node.left = buildTree(nodes)
            node.right = buildTree(nodes)
            return node
        return buildTree(nodes)

We define a Codec class that has two methods, serialize and deserialize. In the serialize method, if the TreeNode is None, we return the string ‘None,’ to indicate a null node. We convert the TreeNode value to a string and concatenate it with a comma separator. We then recursively call the serialize method on the left and right children of the TreeNode. We return the concatenated string.

In the deserialize method, we split the input string by comma separator to obtain a list of node values. We define a recursive helper function buildTree that takes in the list of node values. If the first element in the list is ‘None’, we pop it and return None. Otherwise, we convert the first element to an integer and use it to construct a TreeNode. We then recursively call the buildTree function on the left and right children of the TreeNode. We return the TreeNode.

We call the buildTree function on the list of node values obtained from splitting the input string and return the resulting TreeNode.

Time and Space Complexity: The time complexity of this solution is O(n), where n is the number of nodes in the binary tree, since we visit each node exactly once during serialization and deserialization. The space complexity of this solution is O(n), where n is the number of nodes in the binary tree, since we store the entire tree structure during serialization and deserialization. Therefore, this solution is both time and space-efficient.