-
星空class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if not root: return '' left = self.serialize(root.left) right = self.serialize(root.right) ans = str(root.val) if left: ans += ',' + left if right: ans += ',' + right return ans def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if not data: return None nstack, rstack = [], [0x7FFFFFFF] for val in map(int, data.split(',')): node = TreeNode(val) if nstack: if val < nstack[-1].val: nstack[-1].left = node rstack.append(nstack[-1].val) else: while val > rstack[-1]: while nstack[-1].val > nstack[-2].val: nstack.pop() rstack.pop() nstack.pop() nstack[-1].right = node nstack.append(node) return nstack[0] -
星空
class Codec: def serialize(self, root): def preorder(node): if node: vals.append(str(node.val)) preorder(node.left) preorder(node.right) vals = [] preorder(root) return ' '.join(vals) def deserialize(self, data): preorder = map(int, data.split()) inorder = sorted(preorder) return self.buildTree(preorder, inorder) def buildTree(self, preorder, inorder): def build(stop): if inorder and inorder[-1] != stop: root = TreeNode(preorder.pop()) root.left = build(root.val) inorder.pop() root.right = build(stop) return root preorder.reverse() inorder.reverse() return build(None) -
原题： https://leetcode.com/problems/serialize-and-deserialize-bst/description/
题意： 序列化是指将数据结构或者对象转换为比特序列，使其可以保存在文件或者内存缓冲区中，也可以通过网络链路传输给本机或者其他计算机，在之后进行重构。设计算法序列化/反序列化一棵二叉搜索树。
约定： （1）对序列化/反序列化算法的具体实现没有限制 （2）确保一棵二叉树可以序列化成字符串，字符串可以反序列化为原始二叉树 （3）编码的字符串应该尽可能紧凑 （4）不要使用类成员/全局变量/静态变量来保存状态。你的序列化/反序列化算法应该是无状态的
标签： 序列化、deserialize、serialize、bst、一棵、面试
猜你感兴趣的圈子：
