5. Serialize and Deserialize Binary Tree

297.Serialize and Deserialize Binary Tree

449. Serialize and Deserialize BST

This is your coding interview problem for today.

This problem was asked by Google.

Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.

For example, given the following Node class

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The following test should pass:

node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'

def serialize(node):

  def r_serialize(node, string):
    if root == None:
      string += 'None'
    else:
      string += str(root.val)
      string += str(r_serialize(root.left, string))
      string += str(r_serialize(root.right, string))

      return string

    return r_serialize(node, "")

  def deserialize(string):

      def r_deserialize(lst):
      if lst[0] == 'None':
        lst.pop(0)
        return None

      root = lst[0]
      lst.pop(0)
      root.left = r_deserialize(lst)
      root.right = r_deserialize(lst)
      return root

    data_list = string.split(',')
    return r_deserialize(data_list)

O(N) time and space, since we iterate over the whole tree when serializing and deserializing

def serialize(node):
  if node == None:
    return "#"
  return '{}{}{}'.format(node.val, serialize(node.left), serialize(node.right))

def deserialize(data):

  def helper():
    # Python next() 函数
    val = next(vals)
    if val = "#":
      return None
    node = node(int(val))
    node.left = helper()
    node.right = helper()
    return node
  # Python iter() 函数
    vals = iter(data.split())
  return helper()