449. Serialize and Deserialize BST——几乎所有树的面试题目都会回到BFS或者DFS，使用BFS，None节点存#

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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

DFS

# 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 root is None:

            return "#"

        return str(root.val) + " " + self.serialize(root.left) + " " + self.serialize(root.right)

    def deserialize(self, data):

        """Decodes your encoded data to tree.

        :type data: str

        :rtype: TreeNode

        """

        data = data.split()

        return self.deserialize_helper(data, [])

    def deserialize_helper(self, data, i):

        if data[i[]] == "#":

            return None

        root = TreeNode(int(data[i[]]))

        i[] +=

        root.left = self.deserialize_helper(data, i)

        i[] +=

        root.right = self.deserialize_helper(data, i)

        return root

# Your Codec object will be instantiated and called as such:

# codec = Codec()

# codec.deserialize(codec.serialize(root))

DFS 2:

# 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 root is None:

            return "#"

        return str(root.val) + " " + self.serialize(root.left) + " " + self.serialize(root.right)

    def deserialize(self, data):

        """Decodes your encoded data to tree.

        :type data: str

        :rtype: TreeNode

        """

        data = data.split()

        if data[0] == '#':

            return None

        node = root = TreeNode(int(data[0]))

        stack = [root]

        i = 1

        while data[i] != '#':

            node.left = TreeNode(int(data[i]))

            stack.append(node.left)

            node = node.left

            i += 1

        while stack:

            node = stack.pop()

            i += 1

            if data[i] != '#':

                node.right = TreeNode(int(data[i]))

                stack.append(node.right)

                node = node.right

                i += 1

                while data[i] != '#':

                    node.left = TreeNode(int(data[i]))

                    stack.append(node.left)

                    node = node.left

                    i += 1

            else:

                node.right = None

        return root

# Your Codec object will be instantiated and called as such:

# codec = Codec()

# codec.deserialize(codec.serialize(root))

BFS

# 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 root is None:

            return ""

        stack = [root]

        ans = str(root.val)

        while stack:

            stack2 = []

            for node in stack:

                if node.left:

                    stack2.append(node.left)

                    ans += " "+str(node.left.val)

                else:

                    ans += " #"

                if node.right:

                    stack2.append(node.right)

                    ans += " " + str(node.right.val)

                else:

                    ans += " #"

            stack = stack2

        return ans

    def deserialize(self, data):

        """Decodes your encoded data to tree.

        :type data: str

        :rtype: TreeNode

        """

        array = data.split()

        if not array:

            return None

        root = TreeNode(int(array[]))

        stack = [root]

        i =

        while stack:

            stack2 = []

            for node in stack:

                if array[i] != '#':

                    node.left = TreeNode(int(array[i]))

                    stack2.append(node.left)

                else:

                    node.left = None

                i +=

                if array[i] != '#':

                    node.right = TreeNode(int(array[i]))

                    stack2.append(node.right)

                else:

                    node.right = None

                i +=

            stack = stack2

        return root

# Your Codec object will be instantiated and called as such:

# codec = Codec()

# codec.deserialize(codec.serialize(root))

巴特西

449. Serialize and Deserialize BST——几乎所有树的面试题目都会回到BFS或者DFS，使用BFS，None节点存#

最新文章

热门文章