Python序列化/反序列化的二叉樹

Question

我想在二叉樹的python中實現序列化/反序列化算法。

這裏是我的代碼：

class Node: 
    count = 1 
    def __init__(self, value): 
     self.value = value 
     self.left = None 
     self.right = None 

    def insert(self, value): 
     if self.value > value: 
      if self.left is None: 
       self.left = Node(value) 
       Node.count += 1 
      else: 
       self.left.insert(value) 
     else: 
      if self.right is None: 
       self.right = Node(value) 
       Node.count += 1 
      else: 
       self.right.insert(value) 

# Using preorder 
def serialize(root, serial): 
    if root != None: 
     serial.append(root.value) 
     serialize(root.left, serial) 
     serialize(root.right, serial) 
    else: 
     serial.append('x') 

def deserialize(newRoot, serial): 
    if serial[0] == 'x': 
     serial.pop(0) 
    else: 
     if len(serial) > 0: 
      newRoot = Node(serial.pop(0)) 
      print(newRoot.value) 
      deserialize(newRoot.left, serial) 
      deserialize(newRoot.right, serial) 

print("This program serializes a tree\n") 

root = Node(3) 
root.insert(1) 
root.insert(2) 
root.insert(4) 
root.insert(5) 
root.insert(0) 

# Serialize 
serial = [] 
serialize(root, serial) 
print(serial) 

# Deserialize 
newRoot = Node(None) 
deserialize(newRoot, serial) 
print(newRoot.value) 

的問題是，newRoot沒有得到通過反序列化，因爲蟒蛇按值傳遞更新。我如何解決這個問題，最好是以最優雅的方式？在C/C++中，我只是將一個指針傳遞給newRoot，它應該相應地更新。謝謝！

Answer 1

您可以返回新創建的節點並將它們分配爲左右節點。另外一個列表中的第一個元素的成本比最後一個元素的成本要高，因此reverse在開始時加入列表，然後在遞歸中使用它將在您的情況下更高性能。所以代碼會變成類似於：

def deserialize(serial): 
    serial.reverse() 
    return _deserialize(serial) 

def _deserialize(serial): 
    if not serial: 
     return None 

    node = None 
    value = serial.pop() 
    if value != 'x': 
     node = Node(value) 
     node.left = _deserialize(serial) 
     node.right = _deserialize(serial) 
    return node 

root = deserialize(serial) 
print(root.value)