python - 向后存储递归结果

Question

我正在解决 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.

这是我到目前为止所拥有的，但我似乎无法使函数序列化将结果(从树的底部向上)存储到字符串中。所以我可以打印结果，只是不存储它......

class Tree:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.ser_str = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Tree(data)
                else:
                    self.left.insert(data)
            elif data >= self.data:
                if self.right is None:
                    self.right = Tree(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def serialize(self):
        if self.left:
            self.left.serialize()
        print(self.data)
        if self.right:
            self.right.serialize()

root = Tree(23)
root.insert(10);root.insert(124);root.insert(101);root.insert(1);root.insert(40)
print("here comes the sun")
test = root.serialize()

Answer 1

正如评论中所指出的，您的方法的问题在于您只是打印数据，但从未将其连接到字符串并返回它。但是，该格式也不允许对树进行明确的反序列化。

如果您不想使用像 json 这样的库，那么您可以采用易于解析的格式，例如 Polish Notation ，其中 a + b 写为 + a b。在树的情况下，data 对应于运算符，left 和 right 分支对应于操作数。

def serialize(t):
    if t is None:
        return "-"
    else:
        return f"{t.data} {serialize(t.left)} {serialize(t.right)}"
    
def deserialize(s):
    if isinstance(s, str): s = iter(s.split())
    # using an iterator of chunks makes this easier
    d = next(s)
    if d == "-":
        return None
    else:
        return Tree(d, deserialize(s), deserialize(s))

(请注意，我创建了这些函数，而不是方法，并向 Tree 构造函数添加了一些可选参数以使代码更简单。)

在使用您的树进行测试时，这会将树序列化为 23 10 1 - - - 124 101 40 - - - -。 (然后我反序列化树并再次序列化它并获得相同的格式，因此反序列化也应该起作用。)您可以添加括号以更好地查看字符串中的树结构: (23 (10 (1 - -) -) (124 (101 (40 - -) -) -))，但即使没有括号，格式也是明确的。

这基本上对应于树的简单前序遍历，而您正在进行中序遍历，就像中缀表示法 a + b 一样，没有括号就不是明确的。中序遍历按排序顺序返回元素，这对于某些用途来说很好，但在这里不行，因为这意味着持有相同元素的不同结构的树将序列化到相同的排序列表。当然，您可以只添加括号，但这会使解析/反序列化变得更加困难。使用括号和按顺序，您的树将是 (((- 1 -) 10 -) 23 (((- 40 -) 101 -) 124 -))。

(注意:即使序列化不明确，您也可以从中重新创建一棵二叉树，但该树的形式会有所不同；特别是，如果您只是将元素插入排序中，它将是一个退化二叉树顺序，因为它们是在您的有序遍历中出现的。)