Problem statement

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

Solution

We can keep tuple of embedded tuples: if we have None we return “#”. Then for every node we return tuple with 3 elements: (node, left child, right child). To deserialize we look at data[0] and connect data[1] as the left children and data[2] as the right children.

Complexity

It is O(n) to serialize and deserialize, even though constant can be around 5.

Code

class Codec:
    def serialize(self, root):
        if not root: return "#"
        return root.val, self.serialize(root.left), self.serialize(root.right)

    def deserialize(self, data):
        if data[0] == "#": return None
        node = TreeNode(data[0])
        node.left = self.deserialize(data[1])
        node.right = self.deserialize(data[2])
        return node

Remrak

There are a lot of different ideas how we can solve this problem:

  1. We can use problem 0105, where we create two traversals: preorder and inorder and reconstruct tree with them.
  2. We can use and dfs traversal: preorder, inorder or postorder with dummy variables # for None nodes.