LeetCode 297: Serialize and Deserialize Binary Tree

Recursive

We serialize the tree in pre-order like: $\texttt{root}(\texttt{left-subtree})[\texttt{right-subtree}]$ . During deserialization, we use a stack to parse nested parentheses or brackets.

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(n)$ .

# 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
        """
        if not root:
            return ""
        if not root.left and not root.right:
            return str(root.val)
        left_child = self.serialize(root.left)
        right_child = self.serialize(root.right)
        return f"{root.val}({left_child})[{right_child}]"
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        l = data.find("(")
        if l < 0:
            return TreeNode(int(data))
        stack = []
        val = None
        sign = 1
        for c in data:
            if c.isdigit():
                val = int(c) if val is None else 10*val+int(c)
            elif c == "-":
                sign = -1
            elif c == "(":
                if val is not None:
                    val = sign * val
                stack.append(TreeNode(val))
                val = None
                sign = 1
                stack.append(c)
            elif c == "[":
                stack.append(c)
            else:
                if val is not None:
                    val = sign * val
                    stack.append(TreeNode(val))
                val = None
                sign = 1
                # subtree: None
                if stack[-1] == "(" or stack[-1] == "[":
                    # throw away ( or [
                    stack.pop()
                    stack.append(None)
                # subtree: root
                elif stack[-2] == "(" or stack[-2] == "[":
                    root = stack.pop()
                    # throw away ( or [
                    stack.pop()
                    stack.append(root)
                # subtree: root, left, right
                else:
                    right_child = stack.pop()
                    left_child = stack.pop()
                    root = stack.pop()
                    # throw away ( or [
                    stack.pop()
                    root.left = left_child
                    root.right = right_child
                    stack.append(root)

        # tree: root, left, right
        right_child = stack.pop()
        left_child = stack.pop()
        root = stack.pop()
        root.left = left_child
        root.right = right_child
        return root
        

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

With preorder as: $``\texttt{root},\texttt{left-subtree},\texttt{right-subtree}"$ , we can deserialize more tersely using recursion:

# 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
        """
        if not root:
            return "None"
        left_child = self.serialize(root.left)
        right_child = self.serialize(root.right)
        return f"{root.val},{left_child},{right_child}"
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def dfs(nodes):
            token = next(nodes)
            if token == "None":
                return None
            root = TreeNode(int(token))
            left_child = dfs(nodes)
            right_child = dfs(nodes)
            root.left = left_child
            root.right = right_child
            return root
        
        nodes = data.split(",")
        return dfs(iter(nodes))
        

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

Iterative

With levelwise travesal, we can (de)serialize iteratively. We use "" as a serialization for None.

# 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
        """
        tree = []
        q = deque([root])
        while q:
            u = q.popleft()
            if u:
                tree.append(str(u.val))
                q.append(u.left)
                q.append(u.right)
            else:
                tree.append("")
                        
        return ",".join(tree)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        
        tokens = iter(data.split(","))
        root = TreeNode(int(next(tokens)))
        q = deque([root])
        while q:
            u = q.popleft()
            if tok := next(tokens):
                left_child = TreeNode(int(tok))
                u.left = left_child
                q.append(left_child)
            if tok := next(tokens):
                right_child = TreeNode(int(tok))
                u.right = right_child
                q.append(right_child)

        return root
        

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

During serialization, we can prune possibly large number of tailing "", saving some space. However, during deserialization, for the queue members, there will not be enough None tokens or "". So, we need to consider StopIteration exception as "".

# 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
        """
        tree = []
        q = deque([root])
        while q:
            u = q.popleft()
            if u:
                tree.append(str(u.val))
                q.append(u.left)
                q.append(u.right)
            else:
                tree.append("")

        while tree and tree[-1] == "":
            tree.pop()
                        
        return ",".join(tree)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def next_token(tokens):
            try:
                return next(tokens)
            except StopIteration:
                return ""

        if not data:
            return None
        
        tokens = iter(data.split(","))
        root = TreeNode(int(next(tokens)))
        q = deque([root])
        while q:
            u = q.popleft()
            if tok := next_token(tokens):
                left_child = TreeNode(int(tok))
                u.left = left_child
                q.append(left_child)
            if tok := next_token(tokens):
                right_child = TreeNode(int(tok))
                u.right = right_child
                q.append(right_child)

        return root
        

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

unreasonably effective