Leetcode 449. Serialize and Deserialize BST

题目

解法

按照特定顺序（比如前序遍历）进行serialize，也按照同样的方式进行deserialize，就能保证还原的顺序。

class Codec:def serialize(self, root: Optional[TreeNode]) -> str:"""Encodes a tree to a single string."""if not root:return 'X'left = self.serialize(root.left)right = self.serialize(root.right)return str(root.val) + ',' + left + ',' + rightdef helper(self,arr):front = arr.pop(0)if front == 'X':return Nonenode = TreeNode(int(front))node.left = self.helper(arr)node.right = self.helper(arr)return nodedef deserialize(self, data: str) -> Optional[TreeNode]:"""Decodes your encoded data to tree."""return self.helper(data.split(','))

但是这个题目有几个点不是特别清晰：

• 首先为什么要将字符串转化成list在进行deserialize，其中的原因在于其实list是个对象，在deserialize的时候其实这个list在不断的变短，看上面的implementation可以知道，在helper中进行left和right操作时，实际上这个arr在不断变短。这是因为list是对象属性，所以可以在递归中被不断修改，而字符串则不行，或许字符串也可以操作，但肯定操作相对复杂
• 其次是看起来这种做法对任意一棵树都可以做，并没有因为这是一颗平衡树做了什么优化，所以看起来这并不是最优的做法，应该这道题目还有很多更优化的解法，这个留作后面进行后续思考，这次暂时先到这里
• 这种解法复杂度应该serialize和deserialize都是o(n)，或许理想的复杂度是log级别的