Serialize and Deserialize Binary Tree*

解法二

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Solution

尽量使用按层遍历的方法去做，一层while + queue的方法，需要double check '#' , 根check 一次，left and right check 一次。这道题最容易犯的错误就是不考虑二叉树的不完全情况，很多面试官不会说出来这个前提。这道题在解题的时候，很容易进入一个误区，如果使用中序遍历，所以递归的时候使用前序遍历，便于后面的反序列化。

解法一： 递归法，前序遍历，数组可以reverse下，这样可以直接使用递归，如果使用临时变量i的方法，非常容易出错。

class Codec:

    def serialize(self, root):
        if root == None:
            return []
        result = []

        self.serializeHelper(root, result)

        return result
    def serializeHelper(self, root, result):
        if root == None:
            result.append('#')
            return
        result.append(root.val)
        self.serializeHelper(root.left, result)
        self.serializeHelper(root.right, result)

    def deserialize(self, data):
        if data == None or len(data) == 0:
            return None
        data.reverse()
        return self.deserializeHelper(data)

    def deserializeHelper(self, data):
        val = data.pop()
        if val == '#':
            return None
        root = TreeNode(val)
        root.left = self.deserializeHelper(data)
        root.right = self.deserializeHelper(data)

        return root

class Codec:

    def serialize(self, root):
        if root == None:
            return []
        result = []
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()
            result.append(node.val)
            if node.val != '#':
                if node.left == None:
                    node.left = TreeNode('#')
                if node.right == None:
                    node.right = TreeNode('#')
                queue.append(node.left)
                queue.append(node.right)

        return result

    def deserialize(self, data):
        if data == None or len(data) == 0:
            return None
        i = 0
        root = TreeNode(data[i])
        queue = collections.deque([root])
        rest = []
        while queue and len(data) > i + 2 :
            node = queue.popleft()
            rest.append(node.val)

            if node.val != '#':
                if data[i + 1] != '#':
                    node.left = TreeNode(data[i + 1])
                    queue.append(node.left)
                if data[i + 2] != '#':
                    node.right = TreeNode(data[i + 2])
                    queue.append(node.right)
            i += 2
        return root