Serialize and Deserialize a Binary Tree

题目描述

Simpler Versions of the problem

1. Binary Search Tree

only preorder or postorder and store the structure information

1. complete tree?
2. full tree?
3. how to store a general tree?

We can store preorder and inorder, but double the size. We can use preorder, use # for NULL pointer

解题方法

1. preorder with NULL pointer
2. level order with NULL pointer

Solution

preorder

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        vals_arr = []
        self.serial_helper(root, vals_arr)
        return " ".join(vals_arr)

    def serial_helper(self, root, vals_arr):
        if not root:
            vals_arr.append("#")
        else:
            vals_arr.append(str(root.val))
            self.serial_helper(root.left, vals_arr)
            self.serial_helper(root.right, vals_arr)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        data = iter(data.split()) # 用iterable处理，否则的话用一个全局指针也可以
        return self.deserial_helper(data)

    def deserial_helper(self, data):
        val = next(data)
        if val == "#":
            return None
        else:
            node = TreeNode(int(val))
            node.left = self.deserial_helper(data)
            node.right = self.deserial_helper(data)
        return node

Reference

• geeksforgeeks