python - Python中BST反序列化的错误实现

Question

这是我在 Python 中实现的 BST。

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self, item):
        self.root = self.insert_helper(item, self.root)
        self.size += 1
        return self.root

    def insert_helper(self, item, root):
        if root is None:
            p = Node(item)
            root = p
            return root
        if item > root.data:
            root.right = self.insert_helper(item, root.right)
        else:
            root.left = self.insert_helper(item, root.left)
        return root


class Node:
    def __init__(self, data):
        if data is None:
            raise ValueError('Cannot create Node with None value.')
        self.data = data
        self.left = None
        self.right = None

现在我正在尝试将 BST 序列化和反序列化到列表中，反之亦然。

这是序列化代码。

def serialize(root):
    tree_list = []
    serialize_helper(root, tree_list)
    return tree_list


def serialize_helper(root, tree_list):
    if root is None:
        tree_list.append(sys.maxsize)
        return
    tree_list.append(root.data)
    serialize_helper(root.left, tree_list)
    serialize_helper(root.right, tree_list)

这符合预期。这是反序列化的代码。

def deserialize(tree_list):
    index = 0
    return deserialize_helper(tree_list, index)


def deserialize_helper(tree_list, index):
    if index == len(tree_list) or tree_list[index] == sys.maxsize:
        return None
    root = Node(tree_list[index])
    index += 1
    root.left = deserialize_helper(tree_list, index)
    root.right = deserialize_helper(tree_list, index)
    return root

这段代码有问题，在左右两侧都复制了一个子节点。我调试了代码，似乎当递归结束时索引减少，因此我得到了这种行为。有人可以帮我弄这个吗。

Answer 1

在 Python 中有两大类对象:不可变对象(immutable对象)和可变对象。了解它们的不同之处非常重要:

a = [] # a list, lists are mutable
b = a  # b and a now reference the same object
b.append(1)  # change b and the change will be in-place
print(a)     # since a references the same object
# [1]

a = 1 # an int, ints are immutable
b = a # b and a may well reference the same object, but
b += 1   # since the object cannot change a new object is bound to b
print(a) # leaving a unaffected
# 1

类似地，如果您将一个列表传递给一个函数，并且该函数更改了该列表但没有显式返回它，则这些更改仍然对调用者可见，实际上对持有该列表引用的任何人都是可见的。有些人称之为副作用。您正在序列化程序中使用此技术。

如果您将一个不可变对象(immutable对象)(如您的index)传递给一个函数，并且在该函数内对其进行操作，则原始对象不会改变。它在函数中的名称仅绑定(bind)到调用者不可见的新对象，除非您显式返回它们。

因此，要修复反序列化器，请尝试像这样返回子树和当前索引，

return root, index

所以调用者可以像这样更新他们的

root.left, index = deserialize_helper(tree_list, index)